Isolate the roots, then split them by randomisation
The roots of a polynomial f in the prime field are exactly the roots of gcd(f, xp − x), because xp − x is the product of all linear factors. Computing that GCD requires only one modular exponentiation in the quotient ring. Separating the resulting linear factors from one another is then done by random shifts, which split the roots into residues and non-residues with probability close to one half at each attempt.
Learning objectives
- Reduce root-finding to a single GCD with xp − x.
- Implement equal-degree splitting by random shifts and analyse its success probability.
- Handle the low-degree cases with closed forms.
- Explain why the algorithm is probabilistic in time but never in correctness.
Section 01Isolating the roots
Every element of the prime field satisfies xp = x, so
Therefore gcd(f, xp − x) is the product of the distinct linear factors of f — exactly the roots, each appearing once.
- Make f monic and remove repeated factors: replace f by f / gcd(f, f′).
- Compute xp mod f by modular exponentiation in the ring Fp[x]/(f) — never expand xp as a polynomial.
- Set g ← gcd(f, xp mod f − x).
- The roots of g are precisely the roots of f in Fp; deg g is their number.
Computing xp as a literal polynomial of degree p is catastrophic — for a 64-bit prime the object cannot be stored. The exponentiation must happen in the quotient ring, where every intermediate has degree less than deg f.
Section 02Splitting by random shifts
Once g is a product of distinct linear factors, the roots are separated by exploiting quadratic residuacity: for a random shift a, the polynomial (x + a)(p−1)/2 − 1 vanishes at exactly those roots r for which r + a is a non-zero square.
- If deg g ≤ 1, output the root and return.
- Choose a ∈ Fp uniformly at random.
- Compute h ← gcd(g, (x + a)(p−1)/2 mod g − 1).
- If h is trivial (degree 0 or deg g), return to step 2. A wasted attempt costs one exponentiation.
- Recurse on h and on g/h.
Randomisation affects only the running time. Every factor produced is verified by an exact GCD, so the output is always correct — the algorithm may take longer than expected but never returns a wrong root.
Section 03Low-degree closed forms
| Degree | Method | Notes |
|---|---|---|
| 1 | r = −b/a | One modular inversion |
| 2 | Quadratic formula with a modular square root | Discriminant residuacity decides solvability; needs Tonelli–Shanks when p ≡ 1 (mod 8) |
| 3 | Cardano's formulae, or direct splitting | Requires a cube root; in characteristic 3 the formulae degenerate and must not be used |
| 4 | Resolvent cubic | Reduces to the cubic and quadratic cases |
| ≥ 5 | General algorithm above | No closed form exists; the probabilistic method is the practical choice |
Closed forms assume the characteristic does not divide the relevant denominators. In characteristic 2 the quadratic formula fails outright — the equation must be solved by the additive analogue — and in characteristic 3 the cubic formulae collapse. Guard these cases explicitly.
ReferenceFrequently asked questions
Does this work over an extension field?
Yes, with p replaced by the field size q throughout. The gcd with xq − x still isolates the elements of the base field, and the splitting step uses the appropriate norm map in place of the quadratic residue character.
What if the modulus is composite?
The method breaks, because polynomials over ℤ/nℤ do not form a UFD and GCDs may not exist. In practice an attempted GCD that fails reveals a factor of n — which is useful, but it is not a root-finding algorithm.
Is Berlekamp's algorithm still relevant?
For small p it is excellent, being deterministic and reducing factorisation to a null-space computation of a p-dimensional matrix. For large p the matrix is too big and the Cantor–Zassenhaus style randomised approach dominates.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.