Prof. Dr. Michael Eichberg
Cryptography and Network Security  Principles and Practice, 8th Edition, William Stallings
(((((( Finite Fields in Fields) in Integral Domains) in Commutative Rings) in Rings) in Abelian Groups) in Groups)
A set of elements with a binary operation \(\cdot\) that associates to each ordered pair \((a,b)\) of elements in \(G\) an element \((a \cdot b ) \in G\) , such that the following axioms are obeyed:
If \(a\) and \(b\) belong to \(G\), then \(a \cdot b\) is also in \(G\)
\(a \cdot ( b \cdot c ) = ( a \cdot b ) \cdot c\) for all \(a, b, c \in G\)
There is an element \(e \in G\) such that \(a \cdot e = e \cdot a = a\) for all \(a \in G\)
For each \(a \in G\), there is an element \(a'\) in G such that \(a \cdot a' = a' \cdot a = e\)
(A1 through A4) and:
\(a \cdot b = b \cdot a\) for all \(a, b \in G\)
Exponentiation is defined within a group as a repeated application of the group operator, so that \(a^3 = a \cdot a \cdot a\).
We define \(a^0 = e\) as the identity element, and \(a^{n} = (a')^n\) , where \(a'\) is the inverse element of \(a\) within the group.
A group \(G\) is cyclic if every element of \(G\) is a power \(a^k\) (\(k\) is an integer) of a fixed element \(a \in G\).
The element \(a\) is said to generate the group \(G\) or to be a generator of \(G\).
A cyclic group is always abelian and may be finite or infinite.
A ring \(R\), sometimes denoted by \(\lbrace R , + , \times \rbrace\), is a set of elements with two binary operations, called addition and multiplication, such that for all \(a , b , c \in R\) the axioms (A1A5) are obeyed.
\(R\) is an abelian group with respect to addition; that is, \(R\) satisfies axioms A1 through A5. For the case of an additive group, we denote the identity element as \(0\) and the inverse of \(a\) as \(–a\).
If \(a\) and \(b\) belong to \(R\), then \(ab\) is also in \(R\)
\(a(bc) = (ab)c\) for all \(a,b,c \in R\)
\(a(b+c) = ab+ac\) for all \(a,b,c \in R\)
\((a+b)c = ac+bc\) for all \(a,b,c \in R\)
In essence, a ring is a set in which we can do addition, subtraction \([a  b = a + (b )]\), and multiplication without leaving the set.
A ring is said to be commutative if it satisfies the following additional condition:
\(ab = ba\) for all \(a, b \in R\)
A commutative ring that obeys the following axioms.
There is an element \(1\) in \(R\) such that \(a1 = 1a = a\) for all \(a \in R\)
If \(a,b \in R\) and \(ab = 0\), then either \(a = 0\) or \(b = 0\)
A field \(F\), sometimes denoted by \(\lbrace F, +, \times \rbrace\), is a set of elements with two binary operations, called addition and multiplication, such that for all \(a, b, c \in F\) the axioms (A1–M6) are obeyed.
\(F\) is an integral domain; that is, \(F\) satisfies axioms A1 through A5 and M1 through M6
For each \(a\) in \(F\), except \(0\), there is an element \(a^{1} \in F\) such that \(aa^{1} = (a^{1})a = 1\)
In essence, a field is a set in which we can do addition, subtraction, multiplication, and division without leaving the set. Division is defined with the following rule: \(a/b = a (b^{1})\)
Finite fields play a crucial role in many cryptographic algorithms.
It can be shown that the order of a finite field must be a power of a prime \(p^n\), where \(n\) is a positive integer.
The finite field of order \(p^n\) is generally written \(GF(p^n)\).
GF stands for Galois field, in honor of the mathematician who first studied finite fields.
\(+\) 
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 
\(\times\) 
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 
\(w\) 
\(w\) 
\(w^{1}\) 
0 
0 
\(\) 
1 
7 
1 
2 
6 
\(\) 
3 
5 
3 
4 
4 
\(\) 
5 
3 
5 
6 
2 
\(\) 
7 
1 
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 
\(\times\) 
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 
\(w\) 
\(w\) 
\(w^{1}\) 
0 
0 
\(\) 
1 
6 
1 
2 
5 
4 
3 
4 
5 
4 
3 
2 
5 
2 
3 
6 
1 
6 
\(+\) 
0 
1 
0 
0 
1 
1 
1 
0 
\(\times\) 
0 
1 
0 
0 
0 
1 
0 
1 
\(w\) 
\(w\) 
\(w^{1}\) 
0 
0 
0 
1 
0 
1 
In this section, we have shown how to construct finite fields of order \(p\) where \(p\) is prim.
\(GF(p)\) is defined with the following properties:
\(GF(p)\) consists of \(p\) elements
The binary operations \(+\) and \(\times\) are defined over the set. The operations of addition, subtraction, multiplication, and division can be performed without leaving the set. Each element of the set other than 0 has a multiplicative inverse.
(indeterminate unbestimmte)
If each distinct polynomial is considered to be an element of the set, then that set is a ring.
When polynomial arithmetic is performed on polynomials over a field, then division is possible.
If we attempt to perform polynomial division over a coefficient set that is not a field, we find that division is not always defined.
Even if the coefficient set is a field, polynomial division is not necessarily exact
With the understanding that remainders are allowed, we can say that polynomial division is possible if the coefficient set is a field
We can write any polynomial in the form: \(f(x) = q(x) g(x) + r(x)\)
\(r(x)\) can be interpreted as being a remainder
So \(r(x) = f(x)\; mod\; g(x)\)
If there is no remainder we can say \(g(x)\) divides \(f(x)\)
Written as \(g(x)  f(x)\)
We can say that \(g(x)\) is a factor of \(f(x)\)
Or \(g(x)\) is a divisor of \(f(x)\)
A polynomial \(f(x)\) over a field \(F\) is called irreducible if and only if \(f(x)\) cannot be expressed as a product of two polynomials, both over \(F\), and both of degree lower than that of \(f(x)\).
An irreducible polynomial is also called a prime polynomial.
Polynomial divsion can be defined in terms of multiplication if \(a,b \in F\) then \(a/b = a \times b^{1}\) where \(b^{1}\) is the unique field element such that \(bb^{1} = 1\).
The polynomial \(c(x)\) is said to be the greatest common divisor of \(a(x)\) and \(b(x)\) if the following are true:
\(c(x)\) divides both \(a(x)\) and \(b(x)\)
Any divisor of \(a(x)\) and \(b(x)\) is a divisor of \(c(x)\)
An equivalent definition is:
\(gcd[a(x), b(x)]\) is the polynomial of maximum degree that divides both \(a(x)\) and \(b(x)\)
The Euclidean algorithm can be extended to find the greatest common divisor of two polynomials whose coefficients are elements of a field.
000 
001 
010 
011 
100 
101 
110 
111 

\(+\) 
0 
1 
2 
3 
4 
5 
6 
7 

000 
0 
0 
1 
2 
3 
4 
5 
6 
7 
001 
1 
1 
0 
3 
2 
5 
4 
7 
6 
010 
2 
2 
3 
0 
1 
6 
7 
4 
5 
011 
3 
3 
2 
1 
0 
7 
6 
5 
4 
100 
4 
4 
5 
6 
7 
0 
1 
2 
3 
101 
5 
5 
4 
7 
6 
1 
0 
3 
2 
110 
6 
6 
7 
4 
5 
2 
3 
0 
1 
111 
7 
7 
6 
5 
4 
3 
2 
1 
0 
000 
001 
010 
011 
100 
101 
110 
111 

\(\times\) 
0 
1 
2 
3 
4 
5 
6 
7 

000 
0 
0 
0 
0 
0 
0 
0 
0 
0 
001 
1 
0 
1 
2 
3 
4 
5 
6 
7 
010 
2 
0 
2 
4 
6 
3 
1 
7 
5 
011 
3 
0 
3 
6 
5 
7 
4 
1 
2 
100 
4 
0 
4 
3 
7 
6 
2 
5 
1 
101 
5 
0 
5 
1 
4 
2 
7 
3 
6 
110 
6 
0 
6 
7 
1 
5 
3 
2 
4 
111 
7 
0 
7 
5 
2 
1 
6 
4 
3 
\(w\) 
\(w\) 
\(w^{1}\) 
0 
0 
\(\) 
1 
1 
1 
2 
2 
5 
3 
3 
6 
4 
4 
7 
5 
5 
2 
6 
6 
3 
7 
7 
4 
To construct the finite field \(GF(2^3)\), we need to chose an irreducible polynomial of degree 3. I.e., either \((x^3+x^2+1)\) or \((x^3+x+1)\).
With multiplications modulo x^3 + x + 1, we have only the following eight polynomials in the set of polynomials over \(GF(2)\):
000 
001 
010 
011 
100 
101 
110 
111 

\(+\) 
0 
1 
\(x\) 
\(x+1\) 
\(x^2\) 
\(x^2+1\) 
\(x^2+x\) 
\(x^2+x+1\) 

000 
0 
0 
1 
x 
\(x+1\) 
\(x^2\) 
\(x^2 + 1\) 
\(x^2 + x\) 
\(x^2 + x + 1\) 
001 
1 
1 
0 
\(x+1\) 
x 
\(x^2 + 1\) 
\(x^2\) 
\(x^2 + x + 1\) 
\(x^2 + x\) 
010 
\(x\) 
x 
\(x+1\) 
0 
1 
\(x^2 + x\) 
\(x^2 + x + 1\) 
\(x^2\) 
\(x^2 + 1\) 
011 
\(x+1\) 
\(x+1\) 
x 
1 
0 
\(x^2 + x + 1\) 
\(x^2 + x\) 
\(x^2 + 1\) 
\(x^2\) 
100 
\(x^2\) 
\(x^2\) 
\(x^2 + 1\) 
\(x^2 + x\) 
\(x^2 + x + 1\) 
0 
1 
x 
\(x+1\) 
101 
\(x^2+1\) 
\(x^2 + 1\) 
\(x^2\) 
\(x^2 + x + 1\) 
\(x^2 + x\) 
1 
0 
\(x+1\) 
x 
110 
\(x^2+x\) 
\(x^2 + x\) 
\(x^2 + x + 1\) 
\(x^2\) 
\(x^2 + 1\) 
x 
\(x+1\) 
0 
1 
111 
\(x^2+x+1\) 
\(x^2 + x + 1\) 
\(x^2 + x\) 
\(x^2 + 1\) 
\(x^2\) 
\(x+1\) 
x 
1 
0 
000 
001 
010 
011 
100 
101 
110 
111 

\(\times\) 
0 
1 
\(x\) 
\(x+1\) 
\(x^2\) 
\(x^2+1\) 
\(x^2+x\) 
\(x^2+x+1\) 

000 
0 
0 
0 
0 
0 
0 
0 
0 
0 
001 
1 
0 
1 
\(x\) 
\(x+1\) 
\(x^2\) 
\(x^2 + 1\) 
\(x^2 + x\) 
\(x^2 + x + 1\) 
010 
\(x\) 
0 
\(x\) 
\(x^2\) 
\(x^2 + x\) 
\(x+1\) 
1 
\(x^2 + x + 1\) 
\(x^2 + 1\) 
011 
\(x+1\) 
0 
\(x+1\) 
\(x^2 + x\) 
\(x^2 + 1\) 
\(x^2 + x + 1\) 
\(x^2\) 
1 
\(x\) 
100 
\(x^2\) 
0 
\(x^2\) 
\(x+1\) 
\(x^2 + x + 1\) 
\(x^2 + x\) 
\(x\) 
\(x^2 + 1\) 
1 
101 
\(x^2+1\) 
0 
\(x^2 + 1\) 
1 
\(x^2\) 
\(x\) 
\(x^2 + x + 1\) 
\(x+1\) 
\(x^2 + x\) 
110 
\(x^2+x\) 
0 
\(x^2 + x\) 
\(x^2 + x + 1\) 
1 
\(x^2 + 1\) 
\(x+1\) 
\(x\) 
\(x^2\) 
111 
\(x^2+x+1\) 
0 
\(x^2 + x + 1\) 
\(x^2 + 1\) 
\(x\) 
1 
\(x^2 + x\) 
\(x^2\) 
\(x+1\) 
No simple operation will achieve multiplication in \(GF(2^n)\).
However, a reasonable straightforward technique is available.
Since coefficients are 0 or 1, they can represent any such polynomial as a bit string
Addition becomes XOR of these bit strings
Multiplication is shift and XOR
(cf longhand multiplication)
Modulo reduction is done by repeatedly substituting highest power with remainder of irreducible polynomial (also shift and XOR)