Engineering / Mathematics — Finite Fields
Deterministic Polynomial Factorization Algorithms
Deterministic factorisation over finite fields, the obstacles, and what is known conditionally.
Executive summary
The randomised stage of finite field factorisation has resisted removal. Deterministic polynomial-time factorisation over large finite fields remains open unconditionally.
Under the generalised Riemann hypothesis the problem is solved, and unconditional deterministic methods exist with running times polynomial in the field size rather than its logarithm.
Learning objectives
- Identify precisely which step resists derandomisation.
- State what is known conditionally and unconditionally.
- Situate the problem among similar open questions.
01Where the randomness is needed
Squarefree decomposition and distinct degree factorisation are both deterministic. The obstacle is equal degree splitting, which needs an element behaving differently in different components of the quotient algebra.
The difficulty is closely related to another open problem in this collection: finding a quadratic non-residue modulo a prime deterministically. Both amount to producing an element outside an index-two subgroup, and both are easy at random and open deterministically.
| Stage | Deterministic? | Obstacle |
|---|---|---|
| Squarefree decomposition | Yes | — |
| Distinct degree | Yes | — |
| Equal degree splitting | No | Finding a splitting element |
| Quadratic non-residue | No | The same obstacle in another guise |
02What is known
- Randomised
Polynomial timeCantor-Zassenhaus and Berlekamp - Under GRH
Polynomial timeThe search for a splitting element is bounded - Unconditional, small q
Polynomial timeEnumeration is cheap when q is small - Unconditional, large q
OpenBest methods are polynomial in q, not log q
The conditional result is worth understanding. The generalised Riemann hypothesis bounds the least quadratic non-residue by a polynomial in the logarithm of the modulus, which bounds the search for a splitting element and makes the whole algorithm deterministic.
03Perspective
The situation is a clean example of a gap between randomised and deterministic computation that resists closing, in a setting where the randomised algorithm is simple and fast.
Practical impact
None. The randomised algorithms have failure probabilities driven below hardware fault rates and are used universally.
Theoretical interest
Considerable. It is a natural problem where randomness appears genuinely useful and no derandomisation is known.
Connection to BPP = P
General derandomisation results would resolve it, but they depend on circuit lower bounds that are themselves open.
The broader conjecture is that randomness does not help asymptotically, so a deterministic algorithm should exist. Finding one for this specific problem has been open for decades despite substantial effort, which is a reminder that the conjecture and its instances are separately difficult.
For practical purposes the question is settled: randomised factorisation is fast, reliable, and its error can be made negligible. The open problem is about what is provable, not about what works.
04Frequently asked questions
Why does GRH help here?
Because it bounds the least quadratic non-residue by a polynomial in log p, which bounds the search for a splitting element. The whole difficulty is locating one such element, and GRH says one exists nearby.
Is this related to the AKS breakthrough?
In shape but not in substance. Both concern removing conditions from a deterministic algorithm, and AKS succeeded for primality. The techniques did not transfer to factorisation, which remains open.
Does this affect cryptography?
No. Cryptographic security rests on problems being hard, not on factorisation of polynomials being deterministic. The randomised algorithms are entirely adequate wherever polynomial factorisation is needed.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 483-485.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.