As discussed in the previous tutorial, a finite field is a finite set that is closed under addition, subtraction, multiplication, and division. Galois proved that finite fields exist only when their order (or size of the set) is a prime power pm. When the order is prime, the arithmetic can be mostly computed using integer arithmetic mod p. In the case of prime power order, namely extension fields GF(pm), the finite field arithmetic is computed using polynomials over GF(p) with degree less than m.
The elements of the Galois field GF(pm) can be thought of as the integers {0, 1, …, pm − 1}, although their arithmetic doesn't obey integer arithmetic. A more common interpretation is to view the elements of GF(pm) as polynomials over GF(p) with degree less than m, for instance am − 1xm − 1 + am − 2xm − 2 + … + a1x1 + a0 ∈ GF(p)[x].
For example, consider the finite field GF(32). The order of the field is 9, so we know there are 9 elements. The only question is what to call each element and how to represent them.
python
GF9 = galois.GF(3**2); GF9 print(GF9.properties)
In galois, the default element display mode is the integer representation. This is natural when storing and working with integer numpy arrays. However, there are other representations and at times it may be useful to view the elements in one of those representations.
python
GF9.Elements()
Below, we will view the representation table again to compare and contrast the different equivalent representations.
python
print(GF9.repr_table())
As before, there are some elements whose powers generate the field; we'll skip them for now. The main takeaway from this table is the equivalence of the integer representation and the polynomial (or vector) representation. In GF(32), the element 2α + 1 is a polynomial that can be thought of as 2x + 1 (we'll explain why α is used later). The conversion between the polynomial and integer representation is performed simply by substituting x = 3 into the polynomial 2 * 3 + 1 = 7, using normal integer arithmetic.
With galois, we can represent a single Galois field element using GF9(int) or GF9(string).
python
# Create a single field element from its integer representation GF9(7) # Create a single field element from its polynomial representation GF9("2x + 1") # Create a single field element from its vector representation GF9.Vector([2,1])
In addition to scalars, these conversions work for arrays.
python
GF9([4, 8, 7]) GF9(["x + 1", "2x + 2", "2x + 1"]) GF9.Vector([[1,1], [2,2], [2,1]])
Anytime you have a large array, you can easily view its elements in whichever mode is most illustrative.
python
x = GF9.Elements(); x # Temporarily print x using the power representation with GF9.display("power"): print(x) # Permanently set the display mode to the polynomial representation GF9.display("poly"); x # Reset the display mode to the integer representation GF9.display(); x
# Or convert the (10,) array of GF(p^m) elements to a (10,2) array of vectors over GF(p) x.vector()
In prime fields GF(p), integer arithmetic (addition, subtraction, and multiplication) was performed and then reduced modulo p. In extension fields GF(pm), polynomial arithmetic (addition, subtraction, and multiplication) is performed over GF(p) and then reduced by a polynomial p(x). This polynomial is called an irreducible polynomial because it cannot be factored over GF(p) --an analogue of a prime number.
When constructing an extension field, if an explicit irreducible polynomial is not specified, a default is chosen. The default polynomial is a Conway polynomial which is irreducible and primitive, see galois.conway_poly for more information.
python
p = GF9.irreducible_poly; p galois.is_irreducible(p) # Explicit polynomial factorization returns itself as a multiplicity-1 factor galois.factors(p)
Polynomial addition and subtract never result in polynomials of larger degree, so it is unnecessary to reduce them modulo p(x). Let's try an example of addition. Suppose two field elements a = x + 2 and b = x + 1. These polynomials add degree-wise in GF(p). Relatively easily we can see that a + b = (1 + 1)x + (2 + 1) = 2x. But we can use galois and galois.Poly to confirm this.
python
GF3 = galois.GF(3) # Explicitly create a polynomial over GF(3) to represent a a = galois.Poly([1, 2], field=GF3); a a.integer # Explicitly create a polynomial over GF(3) to represent b b = galois.Poly([1, 1], field=GF3); b b.integer c = a + b; c c.integer
We can do the equivalent calculation directly in the field GF(32).
python
a = GF9("x + 2"); a b = GF9("x + 1"); b c = a + b; c
# Or view the answer in polynomial form with GF9.display("poly"): print(c)
From here, we can view the entire addition arithmetic table. And we can choose to view the elements in the integer representation or polynomial representation.
python
print(GF9.arithmetic_table("+")) with GF9.display("poly"): print(GF9.arithmetic_table("+"))
Polynomial multiplication, however, often results in products of larger degree than the multiplicands. In this case, the result must be reduced modulo p(x).
Let's use the same example from before with a = x + 2 and b = x + 1. To compute c = ab, we need to multiply the polynomials c = (x + 2)(x + 1) = x2 + 2 in GF(3). The issue is that x2 + 2 has degree-2 and the elements of GF(32) can have degree at most 1, hence the need to reduce modulo p(x). After remainder division, we see that c = ab ≡ x mod p.
As before, let's compute this polynomial product explicitly first.
python
# The irreducible polynomial for GF(3^2) p = GF9.irreducible_poly; p # Explicitly create a polynomial over GF(3) to represent a a = galois.Poly([1, 2], field=GF3); a a.integer # Explicitly create a polynomial over GF(3) to represent b b = galois.Poly([1, 1], field=GF3); b b.integer c = (a * b) % p; c c.integer
And now we'll compare that direct computation of this finite field multiplication is equivalent.
python
a = GF9("x + 2"); a b = GF9("x + 1"); b c = a * b; c
# Or view the answer in polynomial form with GF9.display("poly"): print(c)
Now the entire multiplication table can be shown for completeness.
python
- with GF9.display("poly"):
print(GF9.arithmetic_table("*"))
Division, as in GF(p), is a little more difficult. Fortunately the Extended Euclidean Algorithm, which was used in prime fields on integers, can be used for extension fields on polynomials. Given two polynomials a and b, the Extended Euclidean Algorithm finds the polynomials x and y such that xa + yb = gcd(a, b). This algorithm is implemented in galois.egcd.
If a = x + 2 is a field element of GF(32) and b = p(x), the field's irreducible polynomial, then x = a − 1 in GF(32). Note, the GCD will always be 1 because p(x) is irreducible.
python
p = GF9.irreducible_poly; p a = galois.Poly([1, 2], field=GF3); a gcd, x, y = galois.egcd(a, p); gcd, x, y
The claim is that (x + 2) − 1 = x in GF(32) or, equivalently, (x + 2)(x) ≡ 1 mod p(x). This can be easily verified with galois.
python
(a * x) % p
galois performs all this arithmetic under the hood. With galois, performing finite field arithmetic is as simple as invoking the appropriate numpy function or binary operator.
python
a = GF9("x + 2"); a np.reciprocal(a) a ** -1
# Or view the answer in polynomial form with GF9.display("poly"): print(a ** -1)
And finally, for completeness, we'll include the division table for GF(32). Note, division is not defined for y = 0.
python
- with GF9.display("poly"):
print(GF9.arithmetic_table("/"))
A property of finite fields is that some elements can produce the entire field by their powers. Namely, a primitive element g of GF(pm) is an element such that GF(pm) = {0, g0, g1, …, gpm − 1}.
In galois, the primitive elements of an extension field can be found by the class attribute galois.FieldClass.primitive_element and galois.FieldClass.primitive_elements.
python
# Switch to polynomial display mode GF9.display("poly"); p = GF9.irreducible_poly; p GF9.primitive_element GF9.primitive_elements
This means that x, x + 2, 2x, and 2x + 1 can all generate the nonzero multiplicative group GF(32)×. We can examine this by viewing the representation table using different generators.
Here is the representation table using the default generator g = x.
python
print(GF9.repr_table())
And here is the representation table using a different generator g = 2x + 1.
python
print(GF9.repr_table(GF9("2x + 1")))
All other elements cannot generate the multiplicative subgroup. Another way of putting that is that their multiplicative order is less than pm − 1. For example, the element e = x + 1 has ord(e) = 4. This can be seen because e4 = 1.
python
print(GF9.repr_table(GF9("x + 1")))
Some irreducible polynomials have special properties, these are primitive polynomial. A degree-m polynomial is primitive over GF(p) if it has as a root that is a generator of GF(pm).
In galois, the default choice of irreducible polynomial is a Conway polynomial, which is also a primitive polynomial. Consider the finite field GF(24). The Conway polynomial for GF(24) is C2, 4 = x4 + x + 1, which is irreducible and primitive.
python
GF16 = galois.GF(2**4) print(GF16.properties)
Since p(x) = C2, 4 is primitive, it has the primitive element of GF(24) as a root.
python
p = GF16.irreducible_poly; p galois.is_irreducible(p) galois.is_primitive(p) # Evaluate the irreducible polynomial over GF(2^4) at the primitive element p(GF16.primitive_element, field=GF16)
Since the irreducible polynomial is primitive, we write the field elements in polynomial basis with indeterminate α instead of x, where α represents the primitive element of GF(pm). For powers of α less than 4, it can be seen that α = x, α2 = x2, and α3 = x3.
python
print(GF16.repr_table())
Extension fields do not need to be constructed from primitive polynomials, however. The polynomial p(x) = x4 + x3 + x2 + x + 1 is irreducible, but not primitive. This polynomial can define arithmetic in GF(24). The two fields (the first defined by a primitive polynomial and the second defined by a non-primitive polynomial) are isomorphic to one another.
python
p = galois.Poly.Degrees([4,3,2,1,0]); p galois.is_irreducible(p) galois.is_primitive(p)
python
GF16_v2 = galois.GF(2**4, irreducible_poly=p) print(GF16_v2.properties)
- with GF16_v2.display("poly"):
print(GF16_v2.primitive_element)
Notice the primitive element of GF(24) with irreducible polynomial p(x) = x4 + x3 + x2 + x + 1 does not have x + 1 as root in GF(24).
python
# Evaluate the irreducible polynomial over GF(2^4) at the primitive element p(GF16_v2.primitive_element, field=GF16_v2)
As can be seen in the representation table, for powers of α less than 4, α ≠ x, α2 ≠ x2, and α3 ≠ x3. Therefore the polynomial indeterminate used is x to distinguish it from α, the primitive element.
python
print(GF16_v2.repr_table())