Pembagian Polinom pada Medan Galois (GF)

Berikut ini merupakan contoh soal pembagian polinomial pada Medan Galois (GF)

(3x⁶ + 7x⁴ + 4x³ + 5) ÷ (x⁴ + 3x³ + 4) dengan GF(11)

Penyelesaian dengan perhitungan manual

didapat hasil bagi seperti pada gambar di atas. Setelah masing-masing koefisien dimodulus 11, didapat

• hasil bagi = 3x² + 2x + 1
• sisa bagi = x³ + 10x² + 3x +1

Catatan: pada penyelesaian di atas, modulus dilakukan di akhir. Namun, sebenarnya modulus dapat dilakukan pada setiap tahap perhitungan. Berikut ini adalah perhitungannya.

Penyelesaian dengan MATLAB

p = 11;
b = [5 0 0 4 7 0 3]; % 3x^6 + 7x^4 + 4x^3 + 5 
a = [4 0 0 3 1];     % x^4 + 3x^3 + 4
[quot, remd] = gfdeconv(b,a,p) % tidak ada titik koma agar hasil pembagian dan sisa bagi ditampilkan
% Check the result.
bnew = gfadd(gfconv(quot,a,p),remd,p);
if isequal(bnew,b)
   disp('Correct.')
end;

Referensi:

1. William Stallings. Cryptography and Network Security: Principles and Practice 5th Edition. Pearson Education, 2011.
2. doc.ic.ac.uk
3. mathworks.com