Motivation
Knowing that a field with symbols exists does not specify its arithmetic. A calculation needs a chosen irreducible polynomial, a coefficient representation, and algorithms for multiplication and division. Conversely, treating a random modulus as irreducible without checking it can create zero divisors and invalidate every later decoding equation.
We will connect the existence theorem to a finite procedure. First compute in a proposed polynomial quotient. Then test whether that quotient is a field using Frobenius powers and polynomial gcds. Finally, use the proven density of irreducibles to search with a prescribed success probability and a bounded amount of randomness. An unsuccessful search reports failure; it never labels an unverified ring as a field.
The last step also distinguishes an irreducible modulus from a primitive multiplicative element. BCH codes need roots of a particular order, and that is an additional condition rather than an automatic consequence of representing the field.
Definitions
Take a given prime and a monic degree- polynomial , with . Represent each residue by its coefficient list , meaning with . Constants embed the prime field. If the modulus is verified irreducible, the quotient is a field of size .
Polynomial division and gcd calculations in this chapter take place over the already known coefficient field . They do not assume that the proposed quotient is a field. Define remainders
Thus is the remainder of . Reducing too keeps the formulas correct for a linear modulus.
The arithmetic representation of one field symbol uses the variable . A message or cyclic word polynomial can use a separate variable , with field elements as coefficients. Reducing a symbol modulo and reducing a cyclic word modulo are different operations in different polynomial rings.
Theorem/proposition
Theorem 14.2.1
(Arithmetic and inverses in a verified quotient)
Add residues coefficientwise modulo . Multiply representatives and reduce the product modulo . A residue represented by is a unit exactly when ; a Bézout identity gives its inverse . In particular, if is irreducible, every nonzero residue has such an inverse.
Theorem 14.2.2
(A finite irreducibility test)
A monic degree- polynomial is irreducible exactly when
For the prime-divisor list is empty. The test has polynomial cost in and using ordinary exact polynomial and modular-integer arithmetic.
Theorem 14.2.3
(Construction with bounded failure and running time)
Given and a rational , a randomized algorithm with running time polynomial in , and the encoding length of (in particular, polynomial in when ) returns an irreducible degree- modulus with probability at least , and otherwise reports failure. Every returned modulus is certified by the deterministic test; the randomization affects discovery, not correctness of a claimed field.
Proof sketch or proof idea
Arithmetic is polynomial arithmetic followed by a remainder
Proof
(Remainders preserve the ring operations)
Division by monic gives one representative of degree less than in each residue class. Adding and multiplying these representatives followed by reduction preserves the ring operations, because multiples of form an ideal. If , reducing gives , proving the inverse formula. Conversely an inverse modulo would give such an identity, so a nonconstant common divisor is impossible.
All these statements remain valid for a reducible modulus, but some nonzero residues can then lack inverses. For example if with smaller positive degrees, the nonzero residues of multiply to zero. A polynomial gcd computation detects the obstruction instead of attempting division by a zero divisor.
For a verified field, ordinary polynomial multiplication followed by long division costs polynomially many prime-field operations. Extended Euclid has polynomial cost as degrees decrease. Exponentiation by a binary integer uses repeated squaring. These procedures operate on lists of residues modulo , with no floating-point rounding. A packed integer label is a storage convention, not permission to substitute arithmetic modulo .
Frobenius separates the possible factor degrees
Proof
(Frobenius divisibility and prime-index gcds)
The preceding existence chapter proved that a monic irreducible of degree divides exactly when . It also proved that this polynomial is squarefree, since its derivative is minus one.
If is irreducible of degree , it divides , so . It divides none of the smaller polynomials at indices , so each displayed gcd is one.
Conversely suppose the tests pass. The first condition makes a divisor of the squarefree polynomial . Its irreducible factors are therefore distinct and have degrees dividing . If one had , choose a prime dividing . Then , so that factor would divide both and , contradicting its gcd test. Hence every factor has degree , and the degree of allows exactly one. This proves irreducibility without assuming the proposed quotient was already a field.
The huge exponent need not be written as a polynomial degree. Iterating keeps every intermediate representative below degree ; each step uses quotient multiplications. There are steps, followed by polynomial gcds. Prime divisors of the integer degree can be found by trial division with cost polynomial in , which is already part of the explicit polynomial-input size. No factorization of is required for this field test.
Proof X-ray
How the two conditions split the work
The final condition says , and by the existence chapter this confines every irreducible factor of to a degree dividing . The gcd conditions then remove the proper divisors, and only a few need checking: every proper divisor of divides a maximal proper divisor with prime, so one gcd per prime divisor of covers all of them. After both steps every irreducible factor has degree , and since there is room for only one; squarefreeness of is convenient but not needed for this count. All divisions take place in , whose coefficient field is already known, so no inverse in the quotient under test is ever used. That is why the argument is not circular.
Each half of the test is needed on its own.
Counterexample mode
The gcd conditions alone do not certify a field
Over take , of prime degree . The only prime divisor of is itself, so the gcd part of the test asks only that , that is, that have no root in . Indeed and . Yet is reducible. The final condition catches it: divides , and it divides only if , so . In the other direction, the quartic in the worked examples passes the final condition but fails a gcd. Only the two conditions together characterize irreducibility, as the theorem states.
Irreducibles are frequent enough for a short search
Proof
(Counting irreducibles and a fixed candidate budget)
Let count monic irreducibles of degree . The previous counting identity gives . For , the proper contribution is . For , the geometric bound on the proper divisors is less than . Thus for every , while for every monic linear polynomial is irreducible and the same lower bound holds.
A uniform random monic degree- polynomial therefore passes the test with probability at least . Choose a positive integer with , and try independent candidates. In the ideal uniform-coefficient experiment, the chance all are reducible is at most
Test every candidate deterministically and return the first that passes. This ideal analysis already gives a fixed candidate budget; the remaining question is how to draw its coefficients with a bounded number of fair bits.
Account for coefficient sampling explicitly
Proof
(Capped coefficient sampling and a coupling)
To sample a coefficient in , draw fair bits and accept the resulting integer if it is below . One attempt succeeds with probability , and an accepted integer is uniform among the choices. Cap each coefficient call at attempts, where . There are at most such calls, so the probability some cap fails is at most .
For rigor, compare the capped algorithm with ideal uncapped coefficient draws on the same fresh attempt bits. They produce the same candidates until a cap failure. A union bound controls this first divergence, without conditioning the whole search on all calls succeeding. Combining the two failure events gives at most . All counters and bit budgets are bounded before execution, and the irreducibility tests are polynomial. Suitable are computed by integer power-of-two comparisons on the rational input, so hidden numerical rounding is unnecessary.
This algorithm certifies a modulus with the stated probability and resource bounds. It does not choose a canonical modulus shared by every implementation; the selected polynomial and basis must still be communicated or fixed as part of an agreed representation.
Concept lensAlgebraic
Two moduli, one field in different coordinates
Different irreducible moduli of degree give isomorphic fields, and an isomorphism is a root. If and are irreducible of degree and is a root of in , then defines a ring map from ; it is injective because the source is a field, hence bijective by counting. For and over , the relation for gives , so is a root of .
Test a multiplicative order separately
Suppose the field is verified and a factorization of is supplied. A nonzero element generates its multiplicative group exactly when
Proof
(Orders divide )
Indeed its order divides . If it were a proper divisor, some prime dividing the quotient would make one displayed power equal one. Conversely an element of order passes every test. For the prime list is empty and the sole nonzero element generates the trivial group.
The order test is efficient given that integer factorization; this is not a claim that factoring every is efficient. If a primitive element is known and , then has order exactly , by the order-of-a-power formula. This explains a standard route to the root-of-unity assumption in a BCH construction while keeping its prerequisites visible.
Worked examples
Worked example 14.2.4
(An explicit inverse in an eight-symbol alphabet)
Over , has no root and is irreducible. Write . Multiplication gives , after the two linear and two constant terms cancel. For division, observe the exact Bézout identity
Thus . The two vectors and multiply to in the basis . Multiplying their packed integer labels modulo eight would be a different calculation in a ring with zero divisors.
Worked example 14.2.5
(Signs in a ternary field)
Take . There is no root of the modulus in , so the quotient is a nine-element field and . We have , whose inverse in the prime field is two. Hence ; direct multiplication gives .
The field's characteristic is three: three copies of add to zero. It is not integer arithmetic modulo nine. Also has order four, not eight, showing why an irreducible modulus does not automatically make its residue variable primitive.
Worked example 14.2.6
(A quartic that passes, and a false shortcut)
For over , successive remainders are , , and . The only prime divisor of four is two, and , so the gcd is one and the test certifies irreducibility.
In contrast passes the final Frobenius check: in its quotient , so . But the smaller test has , giving gcd , not one. The modulus is reducible, and its nonzero residues and multiply to zero. The final Frobenius equality alone cannot distinguish a field from this ring.
Common mistakes
Common mistake
(Keep the two polynomial variables separate)
In a code over , describes the inside of one symbol. A word polynomial has many such symbols as coefficients. Reducing its components modulo does not mean reducing the word polynomial modulo that same polynomial. Cyclic word reduction instead uses , and evaluation substitutes a field element for .
Common mistake
(A packed label is not an integer modulo )
In label by the integer . Then has label and has label , and the first worked example shows that their product is . Multiplying the labels modulo gives , the label of . Worse, , although . Labels are a storage convention; arithmetic acts on the coefficient lists.
Common mistake
(Failing to find a modulus is not a false certificate)
The random search always checks its result. It can fail to find a modulus within the budget, but it cannot return a reducible candidate as a certified field. Increasing its budget changes the failure bound, while the validity criterion remains deterministic. Conversely, an existence proof or a plausible-looking multiplication table is not a certificate of irreducibility.
Summary
Polynomial remainders supply exact symbol arithmetic, and prime-field Euclid supplies inverses. Frobenius remainders and selected gcds certify irreducibility in polynomial time. The density of irreducibles then gives bounded-randomness construction with an explicit failure budget. Multiplicative-order verification is a separate step whose factorization prerequisite must be stated.
Exercises
Quick check
(Why is reduced modulo rather than always stored as the literal polynomial ?)
Consider a modulus of degree one.
Solution
For a linear modulus, already reduces to a constant. The uniform formula compares with that same residue . Comparing a constant remainder with an unreduced degree-one expression would incorrectly reject valid linear moduli.
Quick check
(Which smaller Frobenius indices suffice for the degree-six irreducibility test?)
List the prime divisors of .
Solution
Prime divisors of six are two and three, so indices and suffice, together with the final index six. Any proper factor degree dividing six divides at least one of those two smaller indices and is therefore excluded by a gcd test.
Quick check
(In an eight-element field, why is every nonzero element other than one primitive?)
Find the order of the multiplicative group.
Solution
Its multiplicative group is cyclic of prime order seven. The order of a nonidentity element divides seven and is not one, so it is seven. This special case does not extend to all field sizes, as the nine-element example demonstrates.
Quick check
(Why does the generation algorithm's correctness not depend on the statistical promise that a random candidate is likely irreducible?)
Separate what is returned from how often something is returned.
Solution
Every returned candidate passes an exact necessary-and-sufficient test. The density bound controls only the chance that the bounded search returns a candidate instead of reporting failure. A rare sequence of reducible samples consumes the budget but never produces a false field certificate.