This page implements Galois Fields GF(\(p^n\)) with Python and provides a table of addition. With this \(p\) is a prime number and \(n\) ranges from 1 to \(n-1\). A GF(\(2^4\)) will have a range of outputs from 0 to 15. In this case, we will determine the irreducible polynomial for GF(\(2^3\)), GF(\(3^2\)), GF(\(5^2\)), and a range of other values.
Irreducible_polynomial for GF(\(p^n\)) for a range of \(p\) and \(n\) values |
GF(2²)
For two-bit values, we can represent the values as polynomials:
00 = 0 01 = 1 10 = x 11 = x+1
Now, we can add to get:
00 + 00 -> 0 00 + 01 -> 0 +1 = 1 00 + 10 -> 0 +x = x 00 + 11 -> 0 + (x+1) = x+1 01 + 00 -> 1 + 0 = 1 01 + 01 -> 1+1 = 0 01 + 10 -> 1+x = 1+x 01 + 11 -> 1+ (x+1) = x 10 + 00 -> x+ 0 = 1 10 + 01 -> x+1 = x+1 10 + 10 -> x+x = 0 10 + 11 -> x+ (x+1) = 1 11 + 00 -> (x+1) + 0 = x+1 11 + 01 -> (x+1)+1 = x 11 + 10 -> (x+1)+x = 1 11 + 11 -> (x+1)+ (x+1) = 0
For this we are using an EX-OR operation, and so that 1+1 =0 and x+x=0. The operations then become:
Irreducible Polynomial: Additive group for GF(2^2) + | 0 1 2 3 ------- 0 | [ ][ 1 ][ 1x ][ 1x + 1 ] 1 | [ 1 ][ ][ 1x + 1 ][ 1x ] 2 | [ 1x ][ 1x + 1 ][ ][ 1 ] 3 | [ 1x + 1 ][ 1x ][ 1 ][ ] In terms of numeric values we get: + | 0 1 2 3 ----------- 0 | 0 1 2 3 1 | 1 0 3 2 2 | 2 3 0 1 3 | 3 2 1 0
Everything looks good here, and so we have an additive property. Now let’s try multiplication:
00 * 00 -> 0 00 * 01 -> 0 * 1 = 0 00 * 10 -> 0 * x = 0 00 * 11 -> 0 * (x+1) = 0 01 * 00 -> 1 * 0 = 0 01 * 01 -> 1*1 = 1 01 * 10 -> 1*x = x 01 * 11 -> 1* (x+1) = x+1 10 * 00 -> x* 0 = 0 10 * 01 -> x*1 = x 10 * 10 -> x*x = x² 10 * 11 -> x* (x+1) = x²+x 11 * 00 -> (x+1) *0 = 0 11 * 01 -> (x+1)*1 = x+1 11 * 10 -> (x+1)*x = x²+x 11 * 11 -> (x+1)* (x+1) = x²+x+x+1=x²+1
Now we get a result with x² and must get rid of this in order to stay within the region of 00 to 11. Using a Galois field, note the remainder by dividing by an irreducible polynomial (and which cannot be factorized). For n-bits, we need a polynomial with \(n\) as the highest power. The first three irreducible polynomials are x, x+1 and x²+x+1:
In this case, we can use x²+x+1. Thus for x²+x, we get:
1 ------------- x^2 + x + 1 | x^2 + x x^2 + x + 1 ----------- 1
and gives a remainder of 1. We now get:
Multiplicative group for GF(2^3) + | 0 1 2 3 ------- 0 | [ ][ ][ ][ ] 1 | [ ][ 1 ][ 1x ][ 1x + 1 ] 2 | [ ][ 1x ][ 1x + 1 ][ 1 ] 3 | [ ][ 1x + 1 ][ 1 ][ 1x ]
Converting these into integers, we get:
Multiplicative group for GF(2^3) + | 0 1 2 3 ------- 0 | 0 0 0 0 1 | 0 1 2 3 2 | 0 2 3 1 3 | 0 3 1 2
And we can see that all the outputs are generated. If we use this program:
import galois import sys import io p=2 n=2 if (len(sys.argv)>1): p=int(sys.argv[1]) if (len(sys.argv)>2): n=int(sys.argv[2]) GF = galois.GF(p**n) stdout = sys.stdout f = io.StringIO() print(f"Additive group for GF({p}^{n})") print ("+ | ",end="") for i in range(0,p**n): print("{:2}".format(i),end=" ") print ("\n-------") for i in range(0,p**n): print("{:2}".format(i),end="| ") for j in range(0,p**n): a = GF(i) b = GF(j) print("{:2}".format(a+b),end=" ") print() print("{0}".format(f.getvalue()))
For GF(\(2^2\)), we get:
Additive group for GF(2^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
and for GF(\(2^3\)), we get:
Additive group for GF(2^3) + | 0 1 2 3 4 5 6 7 ------- 0| 0 1 2 3 4 5 6 7 1| 1 0 3 2 5 4 7 6 2| 2 3 0 1 6 7 4 5 3| 3 2 1 0 7 6 5 4 4| 4 5 6 7 0 1 2 3 5| 5 4 7 6 1 0 3 2 6| 6 7 4 5 2 3 0 1 7| 7 6 5 4 3 2 1 0
and for GF(\(2^4\)), we get:
Additive group for GF(2^4) + | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ------- 0| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1| 1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 2| 2 3 0 1 6 7 4 5 10 11 8 9 14 15 12 13 3| 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12 4| 4 5 6 7 0 1 2 3 12 13 14 15 8 9 10 11 5| 5 4 7 6 1 0 3 2 13 12 15 14 9 8 11 10 6| 6 7 4 5 2 3 0 1 14 15 12 13 10 11 8 9 7| 7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 8| 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9| 9 8 11 10 13 12 15 14 1 0 3 2 5 4 7 6 10| 10 11 8 9 14 15 12 13 2 3 0 1 6 7 4 5 11| 11 10 9 8 15 14 13 12 3 2 1 0 7 6 5 4 12| 12 13 14 15 8 9 10 11 4 5 6 7 0 1 2 3 13| 13 12 15 14 9 8 11 10 5 4 7 6 1 0 3 2 14| 14 15 12 13 10 11 8 9 6 7 4 5 2 3 0 1 15| 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0