Assume that q(x) is an
irreducible polynomial of degree n over
GFp; that is, assume that q(x) is of degree n and, whenever
q(x) = a(x)b(x) for some a(x) and b(x) in GFp[x], then either
deg(a(x)) = 0 or
deg(b(x)) = 0. Given two polynomials f (x) and g(x) in
GFp[x], define the product to be the polynomial
(f (x)g(x)modq(x))
modp and the sum to be the polynomial
f (x) + g(x)
modp. With these definitions, the set of
polynomials in GFp[x] of degree less than n forms a field called the
Galois field
GFpn.
The set of polynomials in GF2[x] of degree less than 2 forms the field GF22 = GF4. The multiplication and addition tables for GF2 are given by
× |
+ |
To find the product x⋅x in GF4, reduce the product modulo x2 + x + 1, then reduce the result modulo 2.
Evaluate
(x2modq(x))
mod2 = x + 1
Thus, x2 = x + 1 in GF4. You can generate the entire multiplication table efficiently using matrix and modular arithmetic.
Evaluate (3 times)
=
![]()
modx2 + x + 1
=![]()
mod2 =
Sums require only reduction of polynomial sums modulo 2. The multiplication and addition tables are given by
× |
+ |
× |
+ |
× |
+ |