Perkalian/Pembagian pada Bidang Galois Salah (2^8)

Saya mencoba mengimplementasikan perkalian dan pembagian di GF(2^8) menggunakan tabel log dan eksponensial. Saya menggunakan eksponen 3 sebagai generator saya, menggunakan instruksi dari di sini.

Namun saya gagal dalam beberapa uji kasus sepele.

contoh:

//passes  
assert((GF256elm(4) / GF256elm(1)) == GF256elm(4));  
assert((GF256elm(32) / GF256elm(16)) == GF256elm(2));  
assert((GF256elm(15) / GF256elm(5)) == GF256elm(3));  
assert((GF256elm(88) / GF256elm(8)) == GF256elm(11));  
//fails, but should pass
assert((GF256elm(77) / GF256elm(11)) == GF256elm(7));
assert((GF256elm(77) / GF256elm(7)) == GF256elm(11));

Empat baris pertama lolos, namun gagal pada baris ke-5 dan ke-6.
Setelah diselidiki lebih lanjut saya menemukan bahwa kesalahan ini terjadi ketika ada 'wrap over', yaitu log3(a) + log3(b) > 255 (kasus perkalian) atau log3(a) - log3(b) < 0. Namun nilainya diubah sedemikian rupa sehingga tetap di 0~255 menggunakan modulus sebenarnya.

GF256elm& GF256elm::operator/=(const GF256elm& other) { //C++ operator override for division
    int t = _logTable[val] - _logTable[other.val]; //log3(a) - log3(b)
    int temp =  ((t % 255) + 255) % 255; //this wraps the value to between 0~254 inclusive.
    val = _expTable[temp];
    return *this;
}

operator / diimplementasikan menggunakan override /= di atas sehingga tidak ada hal istimewa yang terjadi di sana.

Saya telah memeriksa apakah tabel log/exp yang dihasilkan sudah benar.

Apa yang kulewatkan di sini? Terima kasih!


c++ cryptography galois-field
person Jacob Wang    schedule 25.08.2013    source sumber
comment
Permintaan maaf saya. ya saya telah menerapkannya dan seharusnya menyebutkannya. Ini pada dasarnya hanya menggunakan /= pada ketentuan LHS dan RHS dan mengembalikan hasilnya jadi tidak ada yang mewah di sana. mengedit jawaban saya.   -  person Jacob Wang    schedule 25.08.2013

Jawaban (3)


arrow_upward
4
arrow_downward

Pertama, bacalah pertanyaan ini dan semua jawaban serta komentarnya dengan cermat:

Penjumlahan dan perkalian di Bidang Galois

Saya pikir kode Anda baik-baik saja, tetapi Anda memiliki dua masalah.

Pertama, komentarnya salah; Anda menjaga eksponen di kisaran 0-254, bukan 0-255.

Kedua, kasus uji "sepele" Anda salah.

Dalam bidang ini, bayangkan bilangan sebagai polinomial yang koefisiennya Anda peroleh dari representasi biner bilangan tersebut. Misalnya, karena 5 = 2^2 + 1, pada kolom ini "5" berarti x^2 + 1.

Jadi "5" * "3" = (x^2 + 1) * (x + 1) = x^3 + x^2 + x + 1, atau "15". Inilah sebabnya mengapa test case Anda assert((GF256elm(15) / GF256elm(5)) == GF256elm(3)); berfungsi. Ini tidak ada hubungannya dengan anggapan umum Anda bahwa lima kali tiga sama dengan lima belas. Demikian pula untuk kasus uji kerja Anda yang lain, yang akan Anda lihat sebagian besar melibatkan kekuatan dua.

Namun, "7" * "11" = (x^2 + x + 1) * (x^3 + x + 1) = x^5 + x^4 + 2x^3 + 2x^2 +2x + 1

Tapi koefisiennya semuanya modulo 2, jadi ini sebenarnya x^5 + x^4 + 1 = "49". Inilah sebabnya mengapa dua kasus uji terakhir Anda gagal.

Jika Anda mencoba assert(GF256elm(49) / GF256elm(7) == GF256elm(11)); Anda akan menemukannya.

person Nemo    schedule 26.08.2013
comment
Saya tahu (dan sengaja) meletakkannya di kisaran 0~254, seperti yang dijelaskan dalam komentar saya. Terima kasih telah menjelaskan konsep perkalian di bidang berhingga. Saya memang telah melakukan uji kasus yang buruk karena kurangnya pemahaman saya tentang bidang yang terbatas. - person Jacob Wang; 26.08.2013
comment
@jtcwang tetapi komentar di kode Anda mengatakan //this wraps the value to between 0~255 - person gx_; 26.08.2013
comment
akan memperbaiki. Terima kasih telah memperhatikan - person Jacob Wang; 06.09.2013

arrow_upward
0
arrow_downward

x % n mengevaluasi ke bilangan bulat antara 0 dan (n - 1), inklusif.

Artinya x % 255 bernilai bilangan bulat antara 0 dan 254, bukan 0 dan 255.

Anda harus mengganti 255 dengan 256, atau sebagai alternatif, melakukan AND secara bitwise dengan 0xff untuk hasil yang sama. Yang terakhir lebih cepat, meskipun kemungkinan besar kompiler cukup pintar untuk mengoptimalkannya ke bytecode yang sama.

person ntoskrnl    schedule 25.08.2013
comment
Omong-omong, ini berlaku tidak hanya untuk C++ % tetapi untuk sisa pembagian bilangan bulat (modulo) secara umum. Presisi: ketika x ditandatangani (misalnya int x), x % 255 dapat dievaluasi menjadi bilangan bulat antara -254 dan 254 (inklusif) (itulah mengapa kode OP adalah ((t % 255) + 255) % 255 dan bukan hanya t % 255). - person gx_; 25.08.2013
comment
Saya sudah mencobanya sebelumnya tetapi tidak berhasil. Dengan pemahaman saya yang terbatas tentang GF(2^8), pola tabel exp/log berulang pada elemen ke-255. yaitu elemen [1] sama dengan [255], sehingga menghasilkan 255 modulus. - person Jacob Wang; 25.08.2013

arrow_upward
0
arrow_downward

Tidak ada yang salah dengan kodenya. Perkalian/pembagian bidang hingga berbeda dengan aritmatika biasa. Silakan lihat pertanyaan ini di cryptostackxchange.

person Jacob Wang    schedule 26.08.2013