This page implements Galois Fields GF(\(2^n\)) with Python and provides a table of additional and multiplication. It outlines GF(\(2^2\)) and GF(\(2^3\)), but also gives a program that can be used for others. Overall, we have the form of GF(\(p^n\)) and which provides use both an additive and a multiplicative group operations that provide all the possible outputs within the finite field. The value of \(p\) is a prime number, and \(n\) is any positive integer. We will display the results of addition and multiplication with binary values.
Additive and Multiplicative Group Table for GF(2^n) - with binary values |
\(\mathbb{Z}_p \pmod n\)
First, let’s start with the problem. In finite fields, we have a \(\pmod n\) operation for a list of integers (\(\mathbb{Z}\)), and where \(n\) is a prime number. This works for our add (+) and multiply (\(\times\)) operations, and where:
\( a \pmod n + b \pmod n = (a+b) \pmod n\)
\(a \pmod n \times b \pmod n = (a \times b) \pmod n\)
If we take \(\mathbb{Z}_7\), we get [here]:
Additive group for Z_7 + | 0 1 2 3 4 5 6 ------- 0 | 0 1 2 3 4 5 6 1 | 1 2 3 4 5 6 0 2 | 2 3 4 5 6 0 1 3 | 3 4 5 6 0 1 2 4 | 4 5 6 0 1 2 3 5 | 5 6 0 1 2 3 4 6 | 6 0 1 2 3 4 5 Multiplicative group for Z_7 * | 0 1 2 3 4 5 6 ------- 0 | 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 2 | 0 2 4 6 1 3 5 3 | 0 3 6 2 5 1 4 4 | 0 4 1 5 2 6 3 5 | 0 5 3 1 6 4 2 6 | 0 6 5 4 3 2 1
We can see that for the additive group, for every permutation, we end up with a different value within the group, and where:
4+0 (mod 7) = 4; 4+1 (mod 7) = 5; 4+2 (mod 7) = 6; 4+3 (mod 7) = 0; 4+4 (mod 7) = 1; and so on.
For multiplicative, we also get all the possible values in the group:
4*0 (mod 7) = 0; 4*1 (mod 7) = 4; 4*2 (mod 7) = 1; 4*3 (mod 7) = 5; and so on.
For the \(-a\) (the inverse addition), we look up the table until we find a zero value as a result. Again, these correspond to all the possible outputs. For the invere multiplication (\(a^{-1}\)) we look up the values which result in 1, and get the inverse multiply of 2 is 4, and the inverse multiply of 3 is 5. But, now let’s test for a non-prime number, such as \(n=8\) (\(\mathbb{Z}_8\)) [here]:
Additive group for Z_8 + | 0 1 2 3 4 5 6 7 ------- 0 | 0 1 2 3 4 5 6 7 1 | 1 2 3 4 5 6 7 0 2 | 2 3 4 5 6 7 0 1 3 | 3 4 5 6 7 0 1 2 4 | 4 5 6 7 0 1 2 3 5 | 5 6 7 0 1 2 3 4 6 | 6 7 0 1 2 3 4 5 7 | 7 0 1 2 3 4 5 6 Multiplicative group for Z_8 * | 0 1 2 3 4 5 6 7 ------- 0 | 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 2 | 0 2 4 6 0 2 4 6 3 | 0 3 6 1 4 7 2 5 4 | 0 4 0 4 0 4 0 4 5 | 0 5 2 7 4 1 6 3 6 | 0 6 4 2 0 6 4 2 7 | 0 7 6 5 4 3 2 1
Now, the additive group is fine, but the multiplicative group does not cycle through all the possible outputs. We see that for \(a=4\) we get:
+ | 0 1 2 3 4 5 6 7 4 | 0 4 0 4 0 4 0 4
Thus \(1 \times 4\pmod 8\) gives 4, and also \(4 \times 3\pmod 8\) also gives 4. This would cause us problems with our cryptography operations, two operations can give the same result.
The coding to implement this is:
import sys n=8 if (len(sys.argv)>1): n=int(sys.argv[1]) print(f"Additive group for Z_{n}") print ("+ | ",end="") for i in range(0,n): print(i,end=" ") print ("\n-------") for i in range(0,n): print (i,end=" | ") for j in range(0,n): print((i+j)%n,end=" ") print() print(f"\nMultiplicative group for Z_{n}") print ("* | ",end="") for i in range(0,n): print(i,end=" ") print ("\n-------") for i in range(0,n): print (i,end=" | ") for j in range(0,n): print((i*j)%n,end=" ") print()
And, so, for \(\mathbb{Z}_p\), we need to use a prime number (p), otherwise, we will not be able to produce unique outputs for all the values of 0 to p-1 for additive and multiplication operations. If we thus has eight-bit values, the nearest prime number is 251. So, what would we do for the values from 252 to 255? Galois solved with his Galois fields, and which used polynomials for operations.
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 [here]:
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 [here]:
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 to 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.
We can convert these into the coefficents of the polynomial with:
res=gf.elm(bits(i))+gf.elm(bits(j)) print("[",res.coeffs,"]",end="")
and our output becomes:
Irreducible Polynomial: [1, 1, 1] Additive group for GF(2^2) + | 0 1 2 3 ------- 0 | [0][1][1 0][1 1] 1 | [1][0][1 1][1 0] 2 | [1 0][1 1][0][1] 3 | [1 1][1 0][1][0] Multiplicative group for GF(2^2) * | 0 1 2 3 ------- 0 | [0][0][0][0] 1 | [0][1][1 0][1 1] 2 | [0][1 0][1 1][1] 3 | [0][1 1][1][1 0]
GF(2³)
And, so, GF(2²) works well. Now let’s try GF(2³). For this, we now have three bits for our values, and which can range from 0 to 7. With 110 we can represent it as x²+x. We will now use this program to generate the output [here]:
from galois_field import GFpn import math import sys def bits(num): bit_list = [(num >> shift_ind) & 1 for shift_ind in range(num.bit_length())] # little endian bit_list.reverse() # big endian return(bit_list) ip4=[1,0,0,1,1] # irreducible polynomial for GF(2^4) - x^4 + x + 1 ip3=[1,0,1,1] # irreducible polynomial for GF(2^3) - x^3+x+1 ip2=[1,1,1] # irreducible polynomial for GF(2^2) - x^2+x+1 p=3 if (len(sys.argv)>1): p=int(sys.argv[1]) ip=ip2 if (p==2): ip=ip2 elif (p==3): ip=ip3 elif (p==4): ip=ip4 gf = GFpn(2,ip ) n=2**p ip_str=gf.elm(ip) print("Irreducible Polynomial: ",ip) print(f"Additive group for GF(2^{p})") print ("+ | ",end="") for i in range(0,n): print(i,end=" ") print ("\n-------") for i in range(0,n): print (i,end=" | ") for j in range(0,n): res=gf.elm(bits(i))+gf.elm(bits(j)) print(res.coeffs,end="") print() print(f"\nMultiplicative group for GF(2^{p})") print ("* | ",end="") for i in range(0,n): print(i,end=" ") print ("\n-------") for i in range(0,n): print (i,end=" | ") for j in range(0,n): res=gf.elm(bits(i))*gf.elm(bits(j)) print(res.coeffs,end="") print()
We can then run for GF(2³) [here]:
Additive group for GF(2^3) + | 0 1 2 3 4 5 6 7 -------------------------------------------------------------------------- 0 | [ 0 ] [ 1 ] [ 1x ] [ 1x + 1 ] [ 1x^2 ] [ 1x^2 + 1 ] [ 1x^2 + 1x ] [ 1x^2 + 1x + 1 ] 1 | [ 1 ] [ 0 ] [ 1x + 1 ] [ 1x ] [ 1x^2 + 1 ] [ 1x^2 ] [ 1x^2 + 1x + 1 ] [ 1x^2 + 1x ] 2 | [ 1x ] [ 1x + 1 ] [ 0 ] [ 1 ] [ 1x^2 + 1x ] [ 1x^2 + 1x + 1 ] [ 1x^2 ] [ 1x^2 + 1 ] 3 | [ 1x + 1 ] [ 1x ] [ 1 ] [ 0 ] [ 1x^2 + 1x + 1 ] [ 1x^2 + 1x ] [ 1x^2 + 1 ] [ 1x^2 ] 4 | [ 1x^2 ] [ 1x^2 + 1 ] [ 1x^2 + 1x ] [ 1x^2 + 1x + 1 ] [ 0 ] [ 1 ] [ 1x ] [ 1x + 1 ] 5 | [ 1x^2 + 1 ] [ 1x^2 ] [ 1x^2 + 1x + 1 ] [ 1x^2 + 1x ] [ 1 ] [ 0 ] [ 1x + 1 ] [ 1x ] 6 | [ 1x^2 + 1x ] [ 1x^2 + 1x + 1 ] [ 1x^2 ] [ 1x^2 + 1 ] [ 1x ] [ 1x + 1 ] [ 0 ] [ 1 ] 7 | [ 1x^2 + 1x + 1 ] [ 1x^2 + 1x ] [ 1x^2 + 1 ] [ 1x^2 ] [ 1x + 1 ] [ 1x ] [ 1 ] [ 0 ] Multiplicative group for GF(2^3) + | 0 1 2 3 4 5 6 7 -------------------------------------------------------------------------- 0 | [ 0 ] [ 0 ] [ 0] [ 0 ] [ 0 ] [ 0 ] [ 0 ] [ 0 ] 1 | [ 0 ] [ 1 ] [ 1x ] [ 1x + 1 ] [ 1x^2 ] [ 1x^2 + 1 ] [ 1x^2 + 1x ] [ 1x^2 + 1x + 1 ] 2 | [ 0 ] [ 1x ] [ 1x^2 ] [ 1x^2 + 1x ] [ 1x + 1 ] [ 1 ] [ 1x^2 + 1x + 1 ] [ 1x^2 + 1 ] 3 | [ 0 ] [ 1x + 1 ] [ 1x^2 + 1x ] [ 1x^2 + 1 ] [ 1x^2 + 1x + 1 ] [ 1x^2 ] [ 1 ] [ 1x ] 4 | [ 0 ] [ 1x^2 ] [ 1x + 1 ] [ 1x^2 + 1x + 1 ] [ 1x^2 + 1x ] [ 1x ] [ 1x^2 + 1 ] [ 1 ] 5 | [ 0 ] [ 1x^2 + 1 ] [ 1 ] [ 1x^2 ] [ 1x ] [ 1x^2 + 1x + 1 ] [ 1x + 1 ] [ 1x^2 + 1x ] 6 | [ 0 ] [ 1x^2 + 1x ] [ 1x^2 + 1x + 1 ] [ 1 ] [ 1x^2 + 1 ] [ 1x + 1 ] [ 1x ] [ 1x^2 ] 7 | [ 0 ] [ 1x^2 + 1x + 1 ] [ 1x^2 + 1 ] [ 1x ] [ 1 ] [ 1x^2 + 1x ] [ 1x^2 ] [ 1x + 1 ]
This translates to [here]:
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 Multiplicative group for GF(2^3) + | 0 1 2 3 4 5 6 7 --------------------- 0 | 0 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 7 2 | 0 2 4 6 3 1 7 5 3 | 0 3 6 5 7 4 1 2 4 | 0 4 3 7 6 2 5 1 5 | 0 5 1 4 2 7 3 6 6 | 0 6 7 1 5 3 2 4 7 | 0 7 5 2 1 6 4 3
We can see that GF(2³) now produces all of the outputs that are possible, such as where 2*5 =1. The value of 1 is the multiplicative inverse (division), and so the multiplicative inverse of 1 is 1, the multiplicative inverse of 2 is 5, the multiplicative inverse of 3 is 6, the multiplicative inverse of 4 is 7, the multiplicative inverse of 6 is 3, and the multiplicative inverse of 7 is 4. This means that we go through all the possible inputs and can get all the possible outputs. For the additive inverse (subtraction), we locate the zero values, and so the additive inverse of 1 is 1, and the additive inverse of 2 is 2.
We can convert these into the coefficents of the polynomial with:
res=gf.elm(bits(i))+gf.elm(bits(j)) print("[",res.coeffs,"]",end="")
and our output becomes:
Irreducible Polynomial: [1, 0, 1, 1] Additive group for GF(2^3) + | 0 1 2 3 4 5 6 7 ------- 0 | [0][1][1 0][1 1][1 0 0][1 0 1][1 1 0][1 1 1] 1 | [1][0][1 1][1 0][1 0 1][1 0 0][1 1 1][1 1 0] 2 | [1 0][1 1][0][1][1 1 0][1 1 1][1 0 0][1 0 1] 3 | [1 1][1 0][1][0][1 1 1][1 1 0][1 0 1][1 0 0] 4 | [1 0 0][1 0 1][1 1 0][1 1 1][0][1][1 0][1 1] 5 | [1 0 1][1 0 0][1 1 1][1 1 0][1][0][1 1][1 0] 6 | [1 1 0][1 1 1][1 0 0][1 0 1][1 0][1 1][0][1] 7 | [1 1 1][1 1 0][1 0 1][1 0 0][1 1][1 0][1][0] Multiplicative group for GF(2^3) * | 0 1 2 3 4 5 6 7 ------- 0 | [0][0][0][0][0][0][0][0] 1 | [0][1][1 0][1 1][1 0 0][1 0 1][1 1 0][1 1 1] 2 | [0][1 0][1 0 0][1 1 0][1 1][1][1 1 1][1 0 1] 3 | [0][1 1][1 1 0][1 0 1][1 1 1][1 0 0][1][1 0] 4 | [0][1 0 0][1 1][1 1 1][1 1 0][1 0][1 0 1][1] 5 | [0][1 0 1][1][1 0 0][1 0][1 1 1][1 1][1 1 0] 6 | [0][1 1 0][1 1 1][1][1 0 1][1 1][1 0][1 0 0] 7 | [0][1 1 1][1 0 1][1 0][1][1 1 0][1 0 0][1 1]GF(2⁴)
We can keep going with GF(p^n), and where p is a prime and n is a positive integer and each of the fields with work for us. Overall, we need to find the correct irreducible polynomial [here]. Now that we have 4 bits we need an irreducible polynomial of x⁴+x+1:
A sample run of the program gives:
Irreducible Polynomial: [1, 0, 0, 1, 1] Additive group for GF(2^p) + | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ------- 0 | [ ][ 1 ][ 1x ][ 1x + 1 ][ 1x^2 ][ 1x^2 + 1 ][ 1x^2 + 1x ][ 1x^2 + 1x + 1 ][ 1x^3 ][ 1x^3 + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ] 1 | [ 1 ][ ][ 1x + 1 ][ 1x ][ 1x^2 + 1 ][ 1x^2 ][ 1x^2 + 1x + 1 ][ 1x^2 + 1x ][ 1x^3 + 1 ][ 1x^3 ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ] 2 | [ 1x ][ 1x + 1 ][ ][ 1 ][ 1x^2 + 1x ][ 1x^2 + 1x + 1 ][ 1x^2 ][ 1x^2 + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^3 ][ 1x^3 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1 ] 3 | [ 1x + 1 ][ 1x ][ 1 ][ ][ 1x^2 + 1x + 1 ][ 1x^2 + 1x ][ 1x^2 + 1 ][ 1x^2 ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x ][ 1x^3 + 1 ][ 1x^3 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 ] 4 | [ 1x^2 ][ 1x^2 + 1 ][ 1x^2 + 1x ][ 1x^2 + 1x + 1 ][ ][ 1 ][ 1x ][ 1x + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 ][ 1x^3 + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ] 5 | [ 1x^2 + 1 ][ 1x^2 ][ 1x^2 + 1x + 1 ][ 1x^2 + 1x ][ 1 ][ ][ 1x + 1 ][ 1x ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1 ][ 1x^3 ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x ] 6 | [ 1x^2 + 1x ][ 1x^2 + 1x + 1 ][ 1x^2 ][ 1x^2 + 1 ][ 1x ][ 1x + 1 ][ ][ 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^3 ][ 1x^3 + 1 ] 7 | [ 1x^2 + 1x + 1 ][ 1x^2 + 1x ][ 1x^2 + 1 ][ 1x^2 ][ 1x + 1 ][ 1x ][ 1 ][ ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x ][ 1x^3 + 1 ][ 1x^3 ] 8 | [ 1x^3 ][ 1x^3 + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ ][ 1 ][ 1x ][ 1x + 1 ][ 1x^2 ][ 1x^2 + 1 ][ 1x^2 + 1x ][ 1x^2 + 1x + 1 ] 9 | [ 1x^3 + 1 ][ 1x^3 ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1 ][ ][ 1x + 1 ][ 1x ][ 1x^2 + 1 ][ 1x^2 ][ 1x^2 + 1x + 1 ][ 1x^2 + 1x ] 10 | [ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^3 ][ 1x^3 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1 ][ 1x ][ 1x + 1 ][ ][ 1 ][ 1x^2 + 1x ][ 1x^2 + 1x + 1 ][ 1x^2 ][ 1x^2 + 1 ] 11 | [ 1x^3 + 1x + 1 ][ 1x^3 + 1x ][ 1x^3 + 1 ][ 1x^3 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x + 1 ][ 1x ][ 1 ][ ][ 1x^2 + 1x + 1 ][ 1x^2 + 1x ][ 1x^2 + 1 ][ 1x^2 ] 12 | [ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 ][ 1x^3 + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^2 ][ 1x^2 + 1 ][ 1x^2 + 1x ][ 1x^2 + 1x + 1 ][ ][ 1 ][ 1x ][ 1x + 1 ] 13 | [ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1 ][ 1x^3 ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x ][ 1x^2 + 1 ][ 1x^2 ][ 1x^2 + 1x + 1 ][ 1x^2 + 1x ][ 1 ][ ][ 1x + 1 ][ 1x ] 14 | [ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^3 ][ 1x^3 + 1 ][ 1x^2 + 1x ][ 1x^2 + 1x + 1 ][ 1x^2 ][ 1x^2 + 1 ][ 1x ][ 1x + 1 ][ ][ 1 ] 15 | [ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x ][ 1x^3 + 1 ][ 1x^3 ][ 1x^2 + 1x + 1 ][ 1x^2 + 1x ][ 1x^2 + 1 ][ 1x^2 ][ 1x + 1 ][ 1x ][ 1 ][ ] Multiplicative group for GF(2^3) + | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ------- 0 | [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ] 1 | [ ][ 1 ][ 1x ][ 1x + 1 ][ 1x^2 ][ 1x^2 + 1 ][ 1x^2 + 1x ][ 1x^2 + 1x + 1 ][ 1x^3 ][ 1x^3 + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ] 2 | [ ][ 1x ][ 1x^2 ][ 1x^2 + 1x ][ 1x^3 ][ 1x^3 + 1x ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1x ][ 1x + 1 ][ 1 ][ 1x^2 + 1x + 1 ][ 1x^2 + 1 ][ 1x^3 + 1x + 1 ][ 1x^3 + 1 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1 ] 3 | [ ][ 1x + 1 ][ 1x^2 + 1x ][ 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x ][ 1x^3 + 1 ][ 1x^3 + 1x + 1 ][ 1x^3 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^2 + 1x + 1 ][ 1x^2 ][ 1 ][ 1x ] 4 | [ ][ 1x^2 ][ 1x^3 ][ 1x^3 + 1x^2 ][ 1x + 1 ][ 1x^2 + 1x + 1 ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^2 + 1x ][ 1x ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x ][ 1x^2 + 1 ][ 1 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1 ] 5 | [ ][ 1x^2 + 1 ][ 1x^3 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^2 + 1x + 1 ][ 1x ][ 1x^3 + 1x^2 + 1 ][ 1x^3 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x + 1 ][ 1x^2 ][ 1 ][ 1x^3 + 1 ][ 1x^3 + 1x^2 ][ 1x + 1 ][ 1x^2 + 1x ] 6 | [ ][ 1x^2 + 1x ][ 1x^3 + 1x^2 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^3 + 1x^2 + 1 ][ 1x^2 + 1x + 1 ][ 1 ][ 1x^2 + 1 ][ 1x + 1 ][ 1x^3 + 1 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 ][ 1x ][ 1x^2 ] 7 | [ ][ 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 ][ 1 ][ 1x^2 + 1x ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x ][ 1x + 1 ][ 1x^2 ][ 1x ][ 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^3 + 1x + 1 ] 8 | [ ][ 1x^3 ][ 1x + 1 ][ 1x^3 + 1x + 1 ][ 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x ][ 1x^2 + 1 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^2 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^2 + 1x + 1 ][ 1x^3 + 1x ][ 1x ][ 1x^3 + 1 ][ 1 ] 9 | [ ][ 1x^3 + 1 ][ 1 ][ 1x^3 ][ 1x ][ 1x^3 + 1x + 1 ][ 1x + 1 ][ 1x^3 + 1x ][ 1x^2 ][ 1x^3 + 1x^2 + 1 ][ 1x^2 + 1 ][ 1x^3 + 1x^2 ][ 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1x ] 10 | [ ][ 1x^3 + 1x ][ 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^2 ][ 1x^3 + 1 ][ 1x + 1 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^2 + 1 ][ 1x^3 ][ 1x ][ 1 ][ 1x^3 + 1x + 1 ][ 1x^2 + 1x ][ 1x^3 + 1x^2 ] 11 | [ ][ 1x^3 + 1x + 1 ][ 1x^2 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x ][ 1 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^2 ][ 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 ][ 1x ][ 1x^3 + 1 ][ 1x^3 + 1x^2 + 1 ][ 1x^2 + 1x ][ 1x^3 ][ 1x + 1 ] 12 | [ ][ 1x^3 + 1x^2 ][ 1x^3 + 1x + 1 ][ 1x^2 + 1x + 1 ][ 1x^2 + 1 ][ 1x^3 + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x ][ 1x^3 + 1x ][ 1x^2 + 1x ][ 1 ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x + 1 ][ 1x^2 ][ 1x^3 ] 13 | [ ][ 1x^3 + 1x^2 + 1 ][ 1x^3 + 1 ][ 1x^2 ][ 1 ][ 1x^3 + 1x^2 ][ 1x^3 ][ 1x^2 + 1 ][ 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x + 1 ][ 1x^2 + 1x ][ 1x + 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x ][ 1x^2 + 1x + 1 ] 14 | [ ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 + 1x + 1 ][ 1 ][ 1x^3 + 1x^2 + 1 ][ 1x + 1 ][ 1x ][ 1x^3 + 1x^2 ][ 1x^3 + 1 ][ 1x^2 + 1x + 1 ][ 1x^2 + 1x ][ 1x^3 ][ 1x^2 ][ 1x^3 + 1x ][ 1x^3 + 1x + 1 ][ 1x^2 + 1 ] 15 | [ ][ 1x^3 + 1x^2 + 1x + 1 ][ 1x^3 + 1x^2 + 1 ][ 1x ][ 1x^3 + 1 ][ 1x^2 + 1x ][ 1x^2 ][ 1x^3 + 1x + 1 ][ 1 ][ 1x^3 + 1x^2 + 1x ][ 1x^3 + 1x^2 ][ 1x + 1 ][ 1x^3 ][ 1x^2 + 1x + 1 ][ 1x^2 + 1 ][ 1x^3 + 1x ]You can check all of these values, and will find that all the possible outputs are generated for additive and multiplication groups and that each has a multiplicative inverse ([1]) and an additive inverse ([ ]).
We can convert these into the coefficents of the polynomial with:
res=gf.elm(bits(i))+gf.elm(bits(j)) print("[",res.coeffs,"]",end="")and our output becomes:
Irreducible Polynomial: [1, 0, 0, 1, 1] 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] ][ [1 0] ][ [1 1] ][ [1 0 0] ][ [1 0 1] ][ [1 1 0] ][ [1 1 1] ][ [1 0 0 0] ][ [1 0 0 1] ][ [1 0 1 0] ][ [1 0 1 1] ][ [1 1 0 0] ][ [1 1 0 1] ][ [1 1 1 0] ][ [1 1 1 1] ] 1 | [ [1] ][ [0] ][ [1 1] ][ [1 0] ][ [1 0 1] ][ [1 0 0] ][ [1 1 1] ][ [1 1 0] ][ [1 0 0 1] ][ [1 0 0 0] ][ [1 0 1 1] ][ [1 0 1 0] ][ [1 1 0 1] ][ [1 1 0 0] ][ [1 1 1 1] ][ [1 1 1 0] ] 2 | [ [1 0] ][ [1 1] ][ [0] ][ [1] ][ [1 1 0] ][ [1 1 1] ][ [1 0 0] ][ [1 0 1] ][ [1 0 1 0] ][ [1 0 1 1] ][ [1 0 0 0] ][ [1 0 0 1] ][ [1 1 1 0] ][ [1 1 1 1] ][ [1 1 0 0] ][ [1 1 0 1] ] 3 | [ [1 1] ][ [1 0] ][ [1] ][ [0] ][ [1 1 1] ][ [1 1 0] ][ [1 0 1] ][ [1 0 0] ][ [1 0 1 1] ][ [1 0 1 0] ][ [1 0 0 1] ][ [1 0 0 0] ][ [1 1 1 1] ][ [1 1 1 0] ][ [1 1 0 1] ][ [1 1 0 0] ] 4 | [ [1 0 0] ][ [1 0 1] ][ [1 1 0] ][ [1 1 1] ][ [0] ][ [1] ][ [1 0] ][ [1 1] ][ [1 1 0 0] ][ [1 1 0 1] ][ [1 1 1 0] ][ [1 1 1 1] ][ [1 0 0 0] ][ [1 0 0 1] ][ [1 0 1 0] ][ [1 0 1 1] ] 5 | [ [1 0 1] ][ [1 0 0] ][ [1 1 1] ][ [1 1 0] ][ [1] ][ [0] ][ [1 1] ][ [1 0] ][ [1 1 0 1] ][ [1 1 0 0] ][ [1 1 1 1] ][ [1 1 1 0] ][ [1 0 0 1] ][ [1 0 0 0] ][ [1 0 1 1] ][ [1 0 1 0] ] 6 | [ [1 1 0] ][ [1 1 1] ][ [1 0 0] ][ [1 0 1] ][ [1 0] ][ [1 1] ][ [0] ][ [1] ][ [1 1 1 0] ][ [1 1 1 1] ][ [1 1 0 0] ][ [1 1 0 1] ][ [1 0 1 0] ][ [1 0 1 1] ][ [1 0 0 0] ][ [1 0 0 1] ] 7 | [ [1 1 1] ][ [1 1 0] ][ [1 0 1] ][ [1 0 0] ][ [1 1] ][ [1 0] ][ [1] ][ [0] ][ [1 1 1 1] ][ [1 1 1 0] ][ [1 1 0 1] ][ [1 1 0 0] ][ [1 0 1 1] ][ [1 0 1 0] ][ [1 0 0 1] ][ [1 0 0 0] ] 8 | [ [1 0 0 0] ][ [1 0 0 1] ][ [1 0 1 0] ][ [1 0 1 1] ][ [1 1 0 0] ][ [1 1 0 1] ][ [1 1 1 0] ][ [1 1 1 1] ][ [0] ][ [1] ][ [1 0] ][ [1 1] ][ [1 0 0] ][ [1 0 1] ][ [1 1 0] ][ [1 1 1] ] 9 | [ [1 0 0 1] ][ [1 0 0 0] ][ [1 0 1 1] ][ [1 0 1 0] ][ [1 1 0 1] ][ [1 1 0 0] ][ [1 1 1 1] ][ [1 1 1 0] ][ [1] ][ [0] ][ [1 1] ][ [1 0] ][ [1 0 1] ][ [1 0 0] ][ [1 1 1] ][ [1 1 0] ] 10 | [ [1 0 1 0] ][ [1 0 1 1] ][ [1 0 0 0] ][ [1 0 0 1] ][ [1 1 1 0] ][ [1 1 1 1] ][ [1 1 0 0] ][ [1 1 0 1] ][ [1 0] ][ [1 1] ][ [0] ][ [1] ][ [1 1 0] ][ [1 1 1] ][ [1 0 0] ][ [1 0 1] ] 11 | [ [1 0 1 1] ][ [1 0 1 0] ][ [1 0 0 1] ][ [1 0 0 0] ][ [1 1 1 1] ][ [1 1 1 0] ][ [1 1 0 1] ][ [1 1 0 0] ][ [1 1] ][ [1 0] ][ [1] ][ [0] ][ [1 1 1] ][ [1 1 0] ][ [1 0 1] ][ [1 0 0] ] 12 | [ [1 1 0 0] ][ [1 1 0 1] ][ [1 1 1 0] ][ [1 1 1 1] ][ [1 0 0 0] ][ [1 0 0 1] ][ [1 0 1 0] ][ [1 0 1 1] ][ [1 0 0] ][ [1 0 1] ][ [1 1 0] ][ [1 1 1] ][ [0] ][ [1] ][ [1 0] ][ [1 1] ] 13 | [ [1 1 0 1] ][ [1 1 0 0] ][ [1 1 1 1] ][ [1 1 1 0] ][ [1 0 0 1] ][ [1 0 0 0] ][ [1 0 1 1] ][ [1 0 1 0] ][ [1 0 1] ][ [1 0 0] ][ [1 1 1] ][ [1 1 0] ][ [1] ][ [0] ][ [1 1] ][ [1 0] ] 14 | [ [1 1 1 0] ][ [1 1 1 1] ][ [1 1 0 0] ][ [1 1 0 1] ][ [1 0 1 0] ][ [1 0 1 1] ][ [1 0 0 0] ][ [1 0 0 1] ][ [1 1 0] ][ [1 1 1] ][ [1 0 0] ][ [1 0 1] ][ [1 0] ][ [1 1] ][ [0] ][ [1] ] 15 | [ [1 1 1 1] ][ [1 1 1 0] ][ [1 1 0 1] ][ [1 1 0 0] ][ [1 0 1 1] ][ [1 0 1 0] ][ [1 0 0 1] ][ [1 0 0 0] ][ [1 1 1] ][ [1 1 0] ][ [1 0 1] ][ [1 0 0] ][ [1 1] ][ [1 0] ][ [1] ][ [0] ] Multiplicative group for GF(2^4) * | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ------- 0 | [ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ][ [0] ] 1 | [ [0] ][ [1] ][ [1 0] ][ [1 1] ][ [1 0 0] ][ [1 0 1] ][ [1 1 0] ][ [1 1 1] ][ [1 0 0 0] ][ [1 0 0 1] ][ [1 0 1 0] ][ [1 0 1 1] ][ [1 1 0 0] ][ [1 1 0 1] ][ [1 1 1 0] ][ [1 1 1 1] ] 2 | [ [0] ][ [1 0] ][ [1 0 0] ][ [1 1 0] ][ [1 0 0 0] ][ [1 0 1 0] ][ [1 1 0 0] ][ [1 1 1 0] ][ [1 1] ][ [1] ][ [1 1 1] ][ [1 0 1] ][ [1 0 1 1] ][ [1 0 0 1] ][ [1 1 1 1] ][ [1 1 0 1] ] 3 | [ [0] ][ [1 1] ][ [1 1 0] ][ [1 0 1] ][ [1 1 0 0] ][ [1 1 1 1] ][ [1 0 1 0] ][ [1 0 0 1] ][ [1 0 1 1] ][ [1 0 0 0] ][ [1 1 0 1] ][ [1 1 1 0] ][ [1 1 1] ][ [1 0 0] ][ [1] ][ [1 0] ] 4 | [ [0] ][ [1 0 0] ][ [1 0 0 0] ][ [1 1 0 0] ][ [1 1] ][ [1 1 1] ][ [1 0 1 1] ][ [1 1 1 1] ][ [1 1 0] ][ [1 0] ][ [1 1 1 0] ][ [1 0 1 0] ][ [1 0 1] ][ [1] ][ [1 1 0 1] ][ [1 0 0 1] ] 5 | [ [0] ][ [1 0 1] ][ [1 0 1 0] ][ [1 1 1 1] ][ [1 1 1] ][ [1 0] ][ [1 1 0 1] ][ [1 0 0 0] ][ [1 1 1 0] ][ [1 0 1 1] ][ [1 0 0] ][ [1] ][ [1 0 0 1] ][ [1 1 0 0] ][ [1 1] ][ [1 1 0] ] 6 | [ [0] ][ [1 1 0] ][ [1 1 0 0] ][ [1 0 1 0] ][ [1 0 1 1] ][ [1 1 0 1] ][ [1 1 1] ][ [1] ][ [1 0 1] ][ [1 1] ][ [1 0 0 1] ][ [1 1 1 1] ][ [1 1 1 0] ][ [1 0 0 0] ][ [1 0] ][ [1 0 0] ] 7 | [ [0] ][ [1 1 1] ][ [1 1 1 0] ][ [1 0 0 1] ][ [1 1 1 1] ][ [1 0 0 0] ][ [1] ][ [1 1 0] ][ [1 1 0 1] ][ [1 0 1 0] ][ [1 1] ][ [1 0 0] ][ [1 0] ][ [1 0 1] ][ [1 1 0 0] ][ [1 0 1 1] ] 8 | [ [0] ][ [1 0 0 0] ][ [1 1] ][ [1 0 1 1] ][ [1 1 0] ][ [1 1 1 0] ][ [1 0 1] ][ [1 1 0 1] ][ [1 1 0 0] ][ [1 0 0] ][ [1 1 1 1] ][ [1 1 1] ][ [1 0 1 0] ][ [1 0] ][ [1 0 0 1] ][ [1] ] 9 | [ [0] ][ [1 0 0 1] ][ [1] ][ [1 0 0 0] ][ [1 0] ][ [1 0 1 1] ][ [1 1] ][ [1 0 1 0] ][ [1 0 0] ][ [1 1 0 1] ][ [1 0 1] ][ [1 1 0 0] ][ [1 1 0] ][ [1 1 1 1] ][ [1 1 1] ][ [1 1 1 0] ] 10 | [ [0] ][ [1 0 1 0] ][ [1 1 1] ][ [1 1 0 1] ][ [1 1 1 0] ][ [1 0 0] ][ [1 0 0 1] ][ [1 1] ][ [1 1 1 1] ][ [1 0 1] ][ [1 0 0 0] ][ [1 0] ][ [1] ][ [1 0 1 1] ][ [1 1 0] ][ [1 1 0 0] ] 11 | [ [0] ][ [1 0 1 1] ][ [1 0 1] ][ [1 1 1 0] ][ [1 0 1 0] ][ [1] ][ [1 1 1 1] ][ [1 0 0] ][ [1 1 1] ][ [1 1 0 0] ][ [1 0] ][ [1 0 0 1] ][ [1 1 0 1] ][ [1 1 0] ][ [1 0 0 0] ][ [1 1] ] 12 | [ [0] ][ [1 1 0 0] ][ [1 0 1 1] ][ [1 1 1] ][ [1 0 1] ][ [1 0 0 1] ][ [1 1 1 0] ][ [1 0] ][ [1 0 1 0] ][ [1 1 0] ][ [1] ][ [1 1 0 1] ][ [1 1 1 1] ][ [1 1] ][ [1 0 0] ][ [1 0 0 0] ] 13 | [ [0] ][ [1 1 0 1] ][ [1 0 0 1] ][ [1 0 0] ][ [1] ][ [1 1 0 0] ][ [1 0 0 0] ][ [1 0 1] ][ [1 0] ][ [1 1 1 1] ][ [1 0 1 1] ][ [1 1 0] ][ [1 1] ][ [1 1 1 0] ][ [1 0 1 0] ][ [1 1 1] ] 14 | [ [0] ][ [1 1 1 0] ][ [1 1 1 1] ][ [1] ][ [1 1 0 1] ][ [1 1] ][ [1 0] ][ [1 1 0 0] ][ [1 0 0 1] ][ [1 1 1] ][ [1 1 0] ][ [1 0 0 0] ][ [1 0 0] ][ [1 0 1 0] ][ [1 0 1 1] ][ [1 0 1] ] 15 | [ [0] ][ [1 1 1 1] ][ [1 1 0 1] ][ [1 0] ][ [1 0 0 1] ][ [1 1 0] ][ [1 0 0] ][ [1 0 1 1] ][ [1] ][ [1 1 1 0] ][ [1 1 0 0] ][ [1 1] ][ [1 0 0 0] ][ [1 1 1] ][ [1 0 1] ][ [1 0 1 0] ]So what?
\(\mathbb{Z}_p\) doesn’t support use well for addition and multiplication as p needs to be a prime number, but GF(\(p^n\)) comes to our rescue, and where we can use GF(2³) for 3-bit values and GF(2⁸) for 8-bit values, and scale to any range that we need. And we have found our solution in GF(p^n). Obviously, we don’t need to use 2 for p, and can use any prime number we want. And when dealing with 8-bit values, such as in AES, we use \(x^8+x^4+x^3+x+1\):
Apart from their usage in AES, Galois fields really come alive in lattice cryptography, and where we use polynomial values to represent points in a lattice. We then operate on these with add, multiply, and multiplicative inverse to perform our cryptographic operations. These are all done by using the irreducible polynomials of our maximum polynomial power.