A finite field or Galois field (GF) has a finite number of elements, and has an order which is equal to a prime number (GF(\(p\))) or to the power of a prime number (GF(\(p^n\))). For example GF(\(2^n\)) has \(2^n\) elements, and its elements are known as binary polynomals (where the co-efficients of the polynomial factors either are either zero or one values. If \(n\) is four, we have 16 output values. GF\((p\)) - the Galois field of \(p\) - is also identified as \(\mathbb{F}_p\), and where we perform arithmetic operations modulo of a prime (\(p\)) [here]. With GF(2) we have modulo 2 operations. For the division, we need to field to be defined with an irreducible polynomial [here].
Addition, Multiplication and Division in Galois Fields GF(\(2^m\)) |
Theory
Let's say we have a number \(a \in \{0,...,2^{n}-1\}\), and represent it as a vector in the form of a polynomial:
\(a=a_0 + a_1 x + a_2 x^2 ... a_{n-1} x^{n-1}\)
If we use \(a_n \in \{0,1\}\), this is exactly the same as representing a binary number modulo \(2^n\). In this \(x^n\) represents bit position \(n\) and \(a_n\) is the value of the bit at position \(x^n\). If a bit is a zero at a given position, it will be not included in the polynomial equation. So, \(1011\) can be represented by \(x^3+x+1\) and \(1010\) is represented as \(x^3+x\). We can then perform arithmetic operations on these polynomial values. So, to add two values of \(1010+1100\) we can represent this as \((x^3+x) + (x^3+x^2)\) and which is \(x^2+x\) as we are using modulo 2 addition, and where \(x^3 + x^3 =0\). With modulo 2 addition, \(0+0=0\), \(0+1=1\), \(1+0=1\), and \(1+1=1\). As the multiplication and division operations can end up with a power which is greater than the field, we divide the output value by a primitive polynomial. Thus the output for \(a \times b\) is completed with \(a \times b \pmod {P(x)}\) and where \(P(x)\) is the primitive polynomial. The primitive polynomial is known as a irreduciable polynomial is it produces the same order of the field.
An example of Galois Fields is within AES (Advanced Encryption Standard) and which uses a finite field GF(\(2^8\)). With AES we operate on bytes (8 bits) in the form of \(b_7b_6b_5b_4b_3b_2b_1b_0\) and which are operated on a a polynomial of \(b_7x^7 + b_6x^6 + b_5x^5 + b_4x^4 + b_3x^3 + b_2x^2 + b_1x^1 + b_0\). In AES, the primitive is \(x^8 + x^4 + x^3 + x + 1\). All the operations in AES are performed on 8-bit values, and thus the complexity is significantly reduced, as apposed to public key methods which can require operations on 100s or 1000s of bits at a time.
With GF(\(2^3\)), we can represent the finite field elements as a power, polynomial, vector, or regular value:
power | polynomial | vector | regular |
0 | 0 | 000 | 0 |
\(x^0\) | 1 | 001 | 1 |
\(x^1\) | x | 010 | 2 |
\(x^2\) | \(x^2\) | 100 | 4 |
\(x^3\) | \(x+1\) | 011 | 3 |
\(x^4\) | \(x^2+x\) | 110 | 6 |
\(x^5\) | \(x^2+x+1\) | 111 | 7 |
\(x^6\) | \(x^2+1\) | 101 | 5 |
Example 1. For \(a=x^2+x+1\) (7 - 111b) and \(b=x+1\) (3 - 011b) with a primitive of \(x^4 + x+1\) (GF(\(2^4\))), for addition we get \(x^2\) (4 - 100b), and for multiplication we get \(x^3+1\) (9 - 1001b).
\(Add = (x^2 + x + 1) + (x +1) = x^2\)
\(Mult = (x^2 + x + 1) \times (x +1) = x^3+x^2+x^2+x+x+1 = x^3+1\)
As we are using modulo 2 addition, then \(x + x = 0\) and \(x^2 + x^2=0\). As the power of the multiplication is not greater than \(x^4\) and above, there is no need to divide by the primitive polynomial. The following is a sample run [here]:
a: 1x^2 + 1x + 1 b: 1x + 1 b^{-1}: 1x^3 + 1x^2 + 1x p: GF(2^4) [1, 0, 0, 1, 1] Add: 1x^2 Subtract: 1x^2 Multiply: 1x^3 + 1 Divide: 1x^3 + 1x^2
For the division, we determine the inverse of \(b\) and then multiply by \(a\). In this case we have \(a \times b^{-1} = (x^2 + x + 1) \times (x^3 + x^2 + x) = x^5 + x^4 + x^3 + x^4 + x^3 + x^2 + x^3 + x^2 + x = x^5 + x^3 + x\). As we have a higher power that the field, we now need to divide by the primitive (\(x^4 + x+1\)) and get the remainder:
__x______ x^4 + x+1 | x^5+ x^3 + x x^5 + x^2 + x -------- x^3+ x^2
This the result of the divide is then the remainder value of \(x^3+x^2\).
Example 2. For \(a=x^3\) (8 - 1000b) and \(b=x^2+1\) (5 - 101b) with a primitive of \(x^4 + x+1\) (GF(\(2^4\))), for addition we get \(x^3 + x^2 + 1\) (13 - 1101b), and for multiplication we get \(x^3 + x^2 + x\) (14 - 1110b).
\(Add = (x^3) + (x^2 +1) = x^3+x2+1\)
\(Mult = (x^3) \times (x^2+1) = x^5+x^3\)
Now we divide \(x^5+x^3\) by the primitive (\(x^4 + x+1\)) and get the remainder:
__x______ x^4 + x+1 | x^5+x^3 x^5 +x^2+x -------- x^3+x^2+x
Thus the result of the multiplication is the remainder of \(x^3+x^2+x\). The following is a sample run [here]:
a: 1x^3 b: 1x^2 + 1 b^{-1}: 1x^3 + 1x + 1 p: GF(2^4) [1, 0, 0, 1, 1] Add: 1x^3 + 1x^2 + 1 Subtract: 1x^3 + 1x^2 + 1 Multiply: 1x^3 + 1x^2 + 1x Divide: 1x^2 + 1x + 1
Example 3. For \(a=x^3+1\) (9 - 1001b) and \(b=x^2+1\) (5 - 101b) with a primitive of \(x^4 + x+1\) (GF(\(2^4\))), for addition we get \(x^3 + x^2 \) (12 - 1100b), and for multiplication we get \(x^3 + x + 1\) (11 - 1011b).
\(Add = (x^3+1) + (x^2+1) = x^3+x^2\)
\(Mult = (x^3+1) \times (x^2+1) = x^5+x^3+x^2+1\)
Now we divide \(x^5+x^3+x^2+1\) by the primitive (\(x^4 + x+1\)) and get the remainder:
__x______ x^4 + x+1 | x^5+ x^3+x^2 +1 x^5 +x^2+x -------- x^3+ x +1
Thus the result of the multiplication is \(x^3+x +1\) (11- 1011b). The following is a sample run [here]:
a: 1x^3 + 1 b: 1x^2 + 1 b^{-1}: 1x^3 + 1x + 1 p: GF(2^4) [1, 0, 0, 1, 1] Add: 1x^3 + 1x^2 Subtract: 1x^3 + 1x^2 Multiply: 1x^3 + 1x + 1 Divide: 1x^3 + 1x^2
Example 4. For \(a=x^2+x+1\) (7 - 0111b) and \(b=x^3+1\) (5 - 1001b) with a primitive of \(x^4 + x+1\) (GF(\(2^4\))), for addition we get \(x^3 + x^2 + 1x\) (14 - 1110b), and for multiplication we get \(x^3 + x\) (11 - 1010b). The following is a sample run [here]:
a: 1x^2 + 1x + 1 b: 1x^3 + 1 b^{-1}: 1x p: GF(2^4) [1, 0, 0, 1, 1] Add: 1x^3 + 1x^2 + 1x Subtract: 1x^3 + 1x^2 + 1x Multiply: 1x^3 + 1x Divide: 1x^3 + 1x^2 + 1x
Example 5. For \(a=x^2 + x\) (6 - 110b) and \(b=x^4 + x^2 + 1\) (21 - 10101b) with a primitive of \(x^6 + x^5 + x^4 + x^3 + x^2 + x\) (GF(\(2^8\))), for addition we get \(1x^4 + 1x + 1\) (19 - 10011b), and for multiplication we get \(x^6 + x^5 + x^4 + x^3 + x^2 + x\). The following is a sample run [here]:
a: 1x^2 + 1x b: 1x^4 + 1x^2 + 1 b^{-1}: 1x^4 + 1x^2 + 1x + 1 p: GF(2^7) [1, 0, 0, 1, 1, 1, 0, 1] Add: 1x^4 + 1x + 1 Subtract: 1x^4 + 1x + 1 Multiply: 1x^6 + 1x^5 + 1x^4 + 1x^3 + 1x^2 + 1x Divide: 1x^6 + 1x^5 + 1x^4 + 1x
With addition, there will be no need for the prime polynomial.
Coding
The code is:
from galois_field import GFpn # Generating the field GF(2^4) # irreducible polynomial. (in this case, x^4 + x+1) import sys a=[1,1,0] b=[0,1,0] p=[1,0,0,1,1] if (len(sys.argv)>1): a=eval("["+sys.argv[1].replace(" ","")+"]") if (len(sys.argv)>2): b=eval("["+sys.argv[2].replace(" ","")+"]") if (len(sys.argv)>3): p=eval("["+sys.argv[3].replace(" ","")+"]") try: gf = GFpn(2,p ) except Exception as e: print ("Error:" ,e) sys.exit() # Generating an element in GF(2^4) aval = gf.elm(a) # x^2+x+1 bval = gf.elm(b) # x # Arithmetic operations aval + bval # 1x^2 + 1 aval - bval # 1x^2 + 1 aval * bval # 1x^3 + 1x^2 + 1x aval / bval # 1x^3 + 1x print ("a:\t\t",aval) print ("b:\t\t",bval) print ("b^{-1}: ",bval.inverse()) print ("p:\t",gf,p) print ("\nAdd:\t\t",aval + bval) print ("Subtract:\t",aval - bval) print ("Multiply:\t",aval * bval) print ("Divide:\t\t",aval / bval)