The Galois Field GFpn

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)$\limfunc$modq(x))$\limfunc$modp and the sum to be the polynomial $\left(\vphantom{
f(x)+g(x)}\right.$f (x) + g(x)$\left.\vphantom{
f(x)+g(x)}\right)$$\limfunc$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

× 0 1 0 0 0 1 0 1    
                
+ 0 1 0 0 1 1 1 0    

The polynomial q(x) = x2 + x + 1 is an (in fact, the only) irreducible polynomial of degree 2 over GF2. The elements of GF4 are 0, 1, x, and 1 + x.

To find the product xx in GF4, reduce the product modulo x2 + x + 1, then reduce the result modulo 2.


$\blacktriangleright$ Evaluate

(x2$\limfunc$modq(x))$\limfunc$mod2 = x + 1


Thus, x2 = x + 1 in GF4. You can generate the entire multiplication table efficiently using matrix and modular arithmetic.


$\blacktriangleright$ Evaluate (3 times)

$\left[\vphantom{
\begin{array}{c}
0 \\
1 \\
x \\
x+1
\end{array}
}\right.$$\begin{array}{c}
0 \\
1 \\
x \\
x+1
\end{array}$$\left.\vphantom{
\begin{array}{c}
0 \\
1 \\
x \\
x+1
\end{array}
}\right]$$\left[\vphantom{
\begin{array}{cccc}
0 & 1 & x & x+1
\end{array}
}\right.$$\begin{array}{cccc}
0 & 1 & x & x+1
\end{array}$$\left.\vphantom{
\begin{array}{cccc}
0 & 1 & x & x+1
\end{array}
}\right]$ = $\left[\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\ ...
...
0 & x+1 & x\left( x+1\right) & \left( x+1\right) ^{2}
\end{array}
}\right.$$\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & x^{2} & ...
...right) \\
0 & x+1 & x\left( x+1\right) & \left( x+1\right) ^{2}
\end{array}$$\left.\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\ ...
...
0 & x+1 & x\left( x+1\right) & \left( x+1\right) ^{2}
\end{array}
}\right]$

$\left[\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\ ...
...
0 & x+1 & x\left( x+1\right) & \left( x+1\right) ^{2}
\end{array}
}\right.$$\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & x^{2} & ...
...right) \\
0 & x+1 & x\left( x+1\right) & \left( x+1\right) ^{2}
\end{array}$$\left.\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\ ...
...
0 & x+1 & x\left( x+1\right) & \left( x+1\right) ^{2}
\end{array}
}\right]$$\func$modx2 + x + 1

                                                             = $\left[\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & -x-1 & -1 \\
0 & x+1 & -1 & x
\end{array}
}\right.$$\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & -x-1 & -1 \\
0 & x+1 & -1 & x
\end{array}$$\left.\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & -x-1 & -1 \\
0 & x+1 & -1 & x
\end{array}
}\right]$

$\left[\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & -x-1 & -1 \\
0 & x+1 & -1 & x
\end{array}
}\right.$$\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & -x-1 & -1 \\
0 & x+1 & -1 & x
\end{array}$$\left.\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & -x-1 & -1 \\
0 & x+1 & -1 & x
\end{array}
}\right]$$\func$mod2 = $\left[\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & x+1 & 1 \\
0 & x+1 & 1 & x
\end{array}
}\right.$$\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & x+1 & 1 \\
0 & x+1 & 1 & x
\end{array}$$\left.\vphantom{
\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & 1 & x & x+1 \\
0 & x & x+1 & 1 \\
0 & x+1 & 1 & x
\end{array}
}\right]$


Sums require only reduction of polynomial sums modulo 2. The multiplication and addition tables are given by

× 0 1 x x + 1 0 0 0 0 0 1 0 1 x x + 1 x 0 x x + 1 1 x + 1 0 x + 1 1 x        

+ 0 1 x x + 1 0 0 1 x x + 1 1 1 0 x + 1 x x x x + 1 0 1 x + 1 x + 1 x 1 0        

Given a polynomial f (x) = ax + b with a and b in GF2, consider the binary representation (ab)2. The binary representations for the multiplication and addition tables for GF4 are given by


× 00 01 10 11 00 00 00 00 00 01 00 01 10 11 10 00 10 11 01 11 00 11 01 10        
            
+ 00 11 10 11 00 00 01 10 11 01 01 00 11 10 10 10 11 00 01 11 11 10 01 00        


Converting from binary to decimal, we have 0 = (00)2, 1 = (01)2, = (10)2, and 3 = $\left(\vphantom{ 11}\right.$11$\left.\vphantom{ 11}\right)_{{2}}^{}$. Using this shorthand notation for polynomials, the multiplication and addition tables become


× 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 3 1 3 0 3 1 2        
            
+ 0 1 2 3 0 0 1 2 3 1 1 0 3 2 2 2 3 0 1 3 3 2 1 0        



\begin{example}
This setting provides the basis for the
Bose-Chaudhuri-Hocqueng...
...mod}%
2=x^{8}+x^{7}+x^{6}+x^{4}+1
\end{displaymath}
\bigskip
\end{example}