A field with eight elements is not the integers modulo eight. That single distinction opens a much larger part of computational number theory. In the integers modulo eight, 2 is nonzero but cannot be inverted. In a field with eight elements, every nonzero element has an inverse. The two systems have the same number of elements and different arithmetic.
To build the field, we do not search for a cleverer way to divide ordinary remainders modulo eight. We change the representation. Elements become short polynomials with coefficients modulo two; multiplication is followed by division by a carefully chosen polynomial. The remainder, rather than the unreduced product, is the stored answer.
This is Guide 9 in the Computational Number Theory series at Bukit Timah Tutor. It develops the arithmetic needed before polynomial factorisation and extension-field algorithms. Readers should be comfortable with polynomial expansion and integer modular inverses. It is an enrichment guide, not a claim about compulsory school syllabus coverage. Return to the BTT Mathematics Hub for school learning, diagnosis and the wider subject map.
The route through this guide
The central worked construction is GF(8), where every calculation can be checked by hand. We then build GF(9) to show which ideas depend on characteristic two and which do not. Along the way, we distinguish fields from rings, irreducible polynomials from primitive polynomials, polynomial coordinates from integer labels, and an efficient calculation from a verified result.
The first half can be read without programming. The implementation section makes one small field executable; it is deliberately not a general-purpose algebra package. The final problems test transfer: can you explain why an operation is valid in one structure and invalid in another, even when their printed symbols look similar?
1. Why arithmetic needs a declared setting
Over the rational numbers, division by any nonzero number is possible. Over the integers, division may leave the integers. Modulo a prime, division by a nonzero residue is again possible. Modulo a composite integer, it may not be. A formula containing a division sign therefore carries an unstated assumption unless its arithmetic setting has been declared.
A field is a commutative arithmetic system with distinct zero and one in which addition, subtraction and multiplication are defined and every nonzero element has a multiplicative inverse. A ring has the addition and multiplication structure but need not have those inverses. These are structural definitions, not descriptions of how large or complicated the elements look.
In Z/8Z, 2·4=0 even though neither factor is zero. If 2 had an inverse u, multiplying that equation by u would give 4=0, a contradiction. The obstruction is not a failed search for u. The arithmetic itself forbids it. Such nonzero factors of zero are called zero divisors.
Finite fields have prime-power size p^m. Their characteristic is p: adding one to itself p times gives zero. The field of size p^m and the integer residue ring modulo p^m coincide only when m=1. The general construction and existence theorem are treated in Shoup’s finite-field chapter. [1]
2. Polynomial coefficients can already be modular
Start with F2={0,1}. Addition is modulo two, so 1+1=0 and subtraction equals addition. Polynomials over F2 still have powers of a formal variable X, but their coefficients belong to this two-element field.
For example, (X²+1)+(X+1)=X²+X. The two constant terms cancel. Multiplication uses ordinary expansion followed by coefficient reduction: (X+1)²=X²+2X+1=X²+1. The middle term vanishes because its coefficient is zero in F2, not because the expansion rule has changed.
Do not reduce powers of X yet. At this stage we are in the polynomial ring F2[X], which contains polynomials of arbitrarily high degree. Reducing coefficients modulo two and reducing polynomials modulo another polynomial are separate operations. Mixing those two stages is a common source of unexplained answers.
The zero polynomial needs special treatment in software because it has no ordinary nonnegative degree. A program may encode its degree as −1 or handle it as a separate case. Either convention works when it is used consistently; treating zero as a degree-zero polynomial with a nonzero leading coefficient does not.
3. Polynomial division replaces integer division
Over any field F, a polynomial A can be divided by a nonzero polynomial M to obtain unique polynomials Q and R with A=QM+R and either R=0 or degree(R)<degree(M). The inverse of the leading coefficient of M allows each cancellation step.
This is long division with the coefficient arithmetic performed in F. For a monic divisor, whose leading coefficient is one, the cancellation is especially simple. The remaining degree decreases at each step, giving a termination argument analogous to the decreasing remainders in integer Euclid.
Choose M=X³+X+1 over F2. In the quotient modulo M, we have X³+X+1=0, hence X³=X+1. Therefore X⁴=X²+X, and X⁵=X³+X²=X²+X+1. A large power has become a polynomial of degree at most two.
The equality X³=X+1 is true in this quotient, not in the unrestricted polynomial ring. Writing the modulus beside the first calculation protects meaning. Once the arithmetic context has been fixed, shorter notation becomes convenient rather than ambiguous.
4. Why the modulus must be irreducible
A nonconstant polynomial M over F is irreducible when it cannot be written as a product of two positive-degree polynomials over F. The quotient F[X]/(M) is a field exactly when M is irreducible. A reducible modulus still defines a quotient ring, but that ring contains nonzero elements without inverses. [1]
For a polynomial of degree two or three, irreducibility is equivalent to having no root in the base field. A reducible quadratic or cubic must have a linear factor; a linear factor corresponds to a root. This shortcut stops being sufficient in degree four, where a product of two irreducible quadratics may have no base-field root.
For M=X³+X+1 over F2, evaluate M(0)=1 and M(1)=1. There is no root, so the cubic is irreducible. The quotient therefore has eight elements and is a field. This small argument is the construction certificate, not merely a convenient preliminary calculation.
Compare M=X²+1 over F2. Here M=(X+1)². In its quotient, the nonzero element X+1 has square zero. Four representatives exist, but their ring is not F4. Counting the representatives alone never proves that a field has been built.
5. Building GF(8) explicitly
Write α for the residue class of X modulo X³+X+1. Then α³=α+1. Every element has a unique expression a0+a1α+a2α² with a0,a1,a2 in F2. There are 2³=8 possible coefficient triples.
0, 1, α, α+1, α², α²+1, α²+α, α²+α+1.
Uniqueness follows from polynomial division. Two different degree-below-three representatives cannot differ by a nonzero multiple of a degree-three polynomial. That fact allows coordinate comparison: two field elements are equal precisely when all three reduced coefficients agree.
Addition is componentwise modulo two. For instance, (α²+α)+(α+1)=α²+1. There are no carries between coordinates. The α-coordinate cancels; it does not turn into a contribution in the α²-coordinate as an ordinary binary integer carry would.
Multiplication has two stages: expand, then replace α³ by α+1 until the degree is below three. A reliable written solution keeps these stages visible until the learner can perform them without confusing a coefficient reduction with a polynomial reduction.
6. A complete multiplication example
Multiply A=α²+1 by B=α+1. First expand without reducing powers:
AB = α³+α²+α+1. α³ = α+1. AB = (α+1)+α²+α+1 = α².
The result is not a guess from a table. Both α terms cancel and both constant terms cancel. The defining polynomial supplies the only nontrivial power reduction. This makes the calculation easy to audit line by line.
Now compare ordinary integer labels. With coefficient encoding a0+2a1+4a2, A has label 5, B has label 3, and the answer α² has label 4. Ordinary 5·3 modulo 8 is 7, not 4. A label identifies an element; it does not determine the arithmetic operation.
This distinction matters whenever data are stored in machine words. Bit patterns may represent field coordinates, ordinary integers, floating-point numbers or instructions. The same printed integer can participate in different operations because the representation contract is different.
7. Powers, order and a small complete cycle
Repeated multiplication by α gives the following exact cycle. Each line can be reconstructed using α³=α+1.
α⁰ = 1 α¹ = α α² = α² α³ = α+1 α⁴ = α²+α α⁵ = α²+α+1 α⁶ = α²+1 α⁷ = 1.
All seven nonzero elements appear before one returns. Therefore α has multiplicative order seven and generates the nonzero multiplicative group. In this particular field, every nonzero element except one has order seven because seven is prime.
The additive behaviour is different: A+A=0 for every A, so every nonzero element has additive order two. There is no contradiction. Additive order concerns repeated addition; multiplicative order concerns repeated multiplication. The operation must accompany the word order.
The discrete-logarithm guide studies the inverse of the power map. Here we use the table only to make the field arithmetic visible, not to present a large inverse-search task.
8. Inverses are polynomial Bézout identities
The extended Euclidean algorithm works for polynomials over a field as well as for integers. Given A and M with gcd(A,M)=1, it finds U and V such that UA+VM=1. Reducing modulo M gives UA=1, so U is the inverse of A in the quotient.
For A=X+1 and M=X³+X+1 over F2, division gives M=(X²+X)(X+1)+1. Rearranging in characteristic two gives 1=M+(X²+X)(X+1). Thus the inverse of α+1 is α²+α.
(α+1)(α²+α) = α³+α²+α²+α = α³+α = (α+1)+α = 1.
This check is short enough to perform independently of the algorithm that found the inverse. The broader mechanism is exactly the one developed for integer modular inverses in Guide 1. The objects changed from integers to polynomials; the Bézout certificate retained its job.
A zero input never has an inverse. If the modulus is reducible, a nonzero input can also fail the gcd test. A correct inverse routine must report that failure instead of continuing as though every nonzero representative belonged to a field.
9. A second route to an inverse
In a finite field with Q elements, every nonzero A satisfies A^(Q−1)=1. Consequently A^(Q−2) is its inverse. For GF(8), inversion can therefore be checked by computing A⁶. [1]
This gives two computational routes: polynomial extended Euclid, or exponentiation. Their relative costs depend on the field representation and implementation. In our tiny classroom field, both are transparent. There is no need to claim that one method is universally fastest.
The exponentiation rule also reveals why the zero case cannot be ignored. Zero raised to a positive power remains zero, so an unguarded computation of A⁶ would return zero rather than identify an inverse failure. An interface should distinguish a valid result from the absence of a mathematical result.
10. Constructing GF(9) without characteristic-two shortcuts
Now use F3 as the coefficient field and M=X²+1. The only squares in F3 are zero and one, so X²+1 has no root. It is an irreducible quadratic. Let β be the class of X; then β²=−1=2.
Every field element is u+vβ with u,v in {0,1,2}. There are nine representatives. Addition remains coordinatewise, but coefficients now reduce modulo three. Subtraction is no longer identical to addition: −β=2β, not β.
Consider (1+β)(2+β). Expansion gives 2+3β+β². The β term vanishes, and β²=2, so the result is 4=1 in F3. Thus 2+β is the inverse of 1+β.
This construction must not be replaced by arithmetic modulo nine. In Z/9Z, 3·3=0; in GF(9), the nonzero element β satisfies β²=2. SageMath’s finite-field constructor documentation explicitly distinguishes field size from the polynomial representation used to realise an extension. [2]
11. Irreducible does not mean primitive
An irreducible degree-m polynomial creates a degree-m field extension. A primitive polynomial additionally has a root that generates the whole nonzero multiplicative group. These are different requirements.
In our GF(9), β²=2 and β⁴=1, while β² is not one. Therefore β has order four, not eight. The defining polynomial is irreducible but β is not a generator of all eight nonzero elements.
On the other hand, (1+β)²=2β, its fourth power is 2, and its eighth power is one. Since the fourth power is not one, its order is eight. A field can be built using a nonprimitive defining root and still contain primitive elements.
This example prevents an important shortcut error: a successful irreducibility test is not a successful primitive-element test. The former concerns polynomial factors; the latter concerns multiplicative order. Software interfaces should name which claim they have established. The finite-field documentation describes both kinds of construction and the role of primitive defining polynomials. [2]
12. Frobenius: a power map that respects addition
In characteristic p, the Frobenius map sends A to A^p. It preserves addition and multiplication, and on a finite field it is an automorphism. The reason addition survives is that the intermediate binomial coefficients in (A+B)^p are divisible by p. [3]
In GF(9), β³=2β. Therefore (u+vβ)³=u+2vβ because u³=u and v³=v in F3. Applying the map twice returns u+vβ, matching the fact that every element satisfies A⁹=A.
In GF(8), Frobenius is squaring. The orbit of α is α, α², α⁴, then α⁸=α. Squaring permutes the field rather than merely making an element larger. There is no compatible ordinary numerical ordering in which that phrase larger would describe field powers.
Frobenius is the bridge to the next guide. Polynomial factorisation algorithms use repeated Frobenius powers and gcds to detect possible factor degrees. A structural map on a field becomes an algorithm for classifying polynomials.
13. Trace and norm return to the base field
For a degree-m extension of Fp, trace adds the Frobenius conjugates and norm multiplies them. These results belong to the base field. They are not ordinary real-variable trace and norm operations imported without adjustment; their definitions depend on the field extension. [3]
Tr(A) = A+A^p+…+A^(p^(m−1)). N(A) = A·A^p·…·A^(p^(m−1)).
For A=u+vβ in our GF(9), the conjugate is u−vβ. Hence Tr(A)=2u and N(A)=(u+vβ)(u−vβ)=u²+v² in F3. For A=1+β, both trace and norm equal 2.
The norm gives another inverse calculation. Divide the conjugate by the nonzero norm: (1+β)^−1=(1−β)/2. Since 2^−1=2 in F3, this becomes 2+β, agreeing with the earlier direct product.
Agreement among independent representations is useful evidence. It does not replace the field axioms or the construction proof, but it catches an arithmetic error that might otherwise survive a single calculation route.
14. A small exact Python laboratory
The following original implementation is deliberately fixed to GF(8)=F2[X]/(X³+X+1). An integer from zero through seven encodes three polynomial coefficients in increasing degree order. Python’s exclusive-or operation performs coefficientwise addition; ordinary integer multiplication is not used as field multiplication.
def multiply_f8(a: int, b: int) -> int:
if type(a) is not int or type(b) is not int:
raise TypeError("Use integer bit encodings.")
if not (0 <= a < 8 and 0 <= b < 8):
raise ValueError("Use integers 0 through 7.")
result = 0
while b:
if b & 1:
result ^= a
a <<= 1
if a & 8:
a ^= 0b1011
b >>= 1
return result
def power_f8(a: int, exponent: int) -> int:
if type(a) is not int or not 0 <= a < 8:
raise ValueError("Use an element encoded from 0 to 7.")
if type(exponent) is not int or exponent < 0:
raise ValueError("Use a nonnegative integer exponent.")
result = 1
while exponent:
if exponent & 1:
result = multiply_f8(result, a)
a = multiply_f8(a, a)
exponent >>= 1
return result
def inverse_f8(a: int) -> int:
if type(a) is not int or not 1 <= a < 8:
raise ValueError("Only nonzero GF(8) elements invert.")
return power_f8(a, 6)
assert multiply_f8(5, 3) == 4
assert multiply_f8(3, 6) == 1
for a in range(1, 8):
assert multiply_f8(a, inverse_f8(a)) == 1The shift by one place multiplies the represented polynomial by X. When an X³ term appears, exclusive-or with binary 1011 subtracts X³+X+1; in characteristic two, subtraction is the same as addition. The high term disappears and the representative returns to degree below three.
The algorithm does not infer irreducibility from the bit pattern. The proof for this particular modulus was supplied earlier. Replacing 1011 by an arbitrary pattern would change the quotient and could destroy the field property. A general library must validate or certify that choice.
15. What the checks establish—and what they do not
The multiplication and power routines were checked on the bounded field used here. All 512 triples of elements were tested for associativity of multiplication and distributivity over exclusive-or addition; all seven nonzero inverse products were checked. Those checks support this small implementation. They are not a proof that an unrelated finite-field package or a modified routine is correct.
A useful personal test is to implement multiplication a second way: expand the two bit-encoded polynomials into coefficient lists, perform a convolution modulo two, then divide by the modulus. Compare the results for all 64 input pairs. Independent implementations make it harder for one shared coding mistake to masquerade as confirmation.
For large fields, exhaustive testing becomes impossible. Then algebraic proofs, small exhaustive tests, random property tests and carefully selected boundary cases serve different roles. The evidence should be described at the scale actually tested.
16. Cost and representation choices
With a polynomial basis of degree m, ordinary multiplication starts from m² coefficient products. Reduction then returns the result to m coordinates. This is a baseline arithmetic count, not a universal running-time claim: coefficient operations themselves cost time, and specialised multiplication methods may change the count.
A power A^e can be computed by repeated squaring using a number of field multiplications proportional to the bit length of positive e. That is the same control pattern as integer modular exponentiation. It does not mean that the entire computation is free of dependence on m or p.
Two isomorphic fields may use different defining polynomials or bases. Their elements can be translated through an isomorphism, but identical coordinate lists do not automatically name corresponding elements. A file exchange should include the characteristic, extension degree, modulus polynomial and coefficient ordering.
This is why field representation is part of the result, not an optional note. A correct tuple interpreted in the wrong field can produce perfectly consistent arithmetic that answers the wrong question.
17. Worked practice: attempt before reading the answers
1. Explain why Z/8Z is not a field. 2. Prove that X³+X+1 is irreducible over F2. 3. List the eight representatives of the resulting field. 4. Compute (α²+α)+(α+1). 5. Compute (α²+1)(α+1). 6. Find the inverse of α+1 and verify it by multiplication.
7. Determine the additive and multiplicative orders of α. 8. Explain why the labels 5 and 3 do not multiply as ordinary integers modulo eight. 9. Show that X²+1 is reducible over F2 but irreducible over F3. 10. In GF(9), compute (1+β)(2+β), where β²=2.
11. Find the orders of β and 1+β in GF(9). 12. Find the Frobenius image of 2+β. 13. Compute the trace and norm of 2+β. 14. Explain why an irreducible defining polynomial need not be primitive. 15. Identify the missing condition in a routine that returns A^(Q−2) for every input. 16. State which metadata are needed to interpret polynomial-coordinate data.
18. Answers with the decisive checks
1. The nonzero residues 2 and 4 multiply to zero. In particular, 2 cannot have an inverse, because multiplying 2·4=0 by that inverse would force 4=0. 2. The cubic is one at both inputs zero and one, so it has no linear factor. A reducible cubic over a field must have a linear factor.
3. The representatives are zero, one, α, α+1, α², α²+1, α²+α and α²+α+1. 4. The answer is α²+1 because the two α terms cancel. 5. Expansion gives α³+α²+α+1; substituting α³=α+1 leaves α².
6. The inverse is α²+α. Its product with α+1 is α³+α=1. 7. The additive order is two, while the displayed power cycle gives multiplicative order seven. 8. The labels encode polynomial coefficients. Field multiplication returns label 4, whereas ordinary 15 modulo eight is 7.
9. Over F2, X²+1=(X+1)². Over F3, substitution at zero, one and two never gives zero; a quadratic with no root is irreducible. 10. The product is 2+3β+β²=2+0+2=1.
11. β²=2 and β⁴=1, so its order is four. The element 1+β has square 2β and fourth power 2, so its order is eight. 12. Cubing gives 2−β=2+2β. 13. Trace is 2·2=1; norm is 2²+1²=2 in F3.
14. Our irreducible X²+1 over F3 has defining root β of order four, while the multiplicative group has eight elements. 15. Inversion requires A to be nonzero; the routine must also know that its arithmetic really is a field. 16. Specify p, m, the defining polynomial, the basis and coefficient order, together with the convention for encoding coefficients.
19. A teaching sequence that tests understanding
Begin by placing Z/8Z beside GF(8) and asking the learner to explain one failed inverse in the former. Then construct the latter from the irreducible cubic. Do not start by memorising the eight-element multiplication table. The goal is to see why the operations work.
Next, ask for the same product in three forms: expanded polynomials, reduced α-expressions and bit encodings. A mismatch identifies the location of an error. Incorrect expansion is different from incorrect reduction, and both differ from a mistaken encoding convention.
Finally, move to GF(9). A learner who silently continues using exclusive-or has transferred the procedure without transferring the condition characteristic two. That is a useful diagnostic failure. The repair is to name the coefficient field before every operation until the distinction becomes automatic.
Sources and further study
[1] Victor Shoup, A Computational Introduction to Number Theory and Algebra, Chapters 17 and 19: polynomial arithmetic and finite-field structure. [2] SageMath, finite-field construction documentation: field size, defining polynomials and compatible representations. [3] SageMath, finite-field base documentation: field elements, Frobenius-related operations, trace, norm and minimal polynomials. The hand computations and fixed GF(8) teaching program above are worked constructions rather than copied software examples.
Continue through Batch 03
Continue to Guide 10: Polynomial Factorisation over Finite Fields for square-free decomposition, Frobenius tests and splitting. Then use Guide 11: p-Adic Valuations and Hensel Lifting for prime-power precision, and Guide 12: Arithmetic Functions, Möbius Inversion and Sieves for exact divisor-based counting.