1 · The essentials
The manuscript presents a fixed, nonrandom procedure for breaking a polynomial into pieces that cannot be broken down further. Its calculations use numbers modulo a prime: numbers with the same remainder are treated as equal. The input must be a nonzero polynomial, supplied as its full list of coefficients, together with the prime written in binary. The procedure returns every smallest polynomial piece and how many times it occurs. The manuscript claims that the number of basic computing steps is bounded by a polynomial in the input-size measure given by the degree plus one, multiplied by the binary length of the prime. It requires neither randomness nor special tools for factoring integers or finding primitive roots, and it does not assume the generalized Riemann hypothesis. The main result is not formalized in Lean and has not been formally verified.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine taking apart an object built from repeated components and listing both the indivisible component types and how many of each were used. Here the object is a polynomial, and the manuscript claims a fixed set of instructions whose running time stays within a polynomial bound in the stated size measure.
Why it matters
The claim combines complete factorization, recovery of repeated factors, and a deterministic polynomial-time bound for every prime field under the stated input conditions. Its scope explicitly excludes reliance on randomness, integer-factorization or primitive-root oracles, and the generalized Riemann hypothesis.
2 · Going further
The precise input is a prime supplied in binary and a nonzero polynomial supplied by its dense coefficient list. Writing , the task is to compute all irreducible factors together with their multiplicities. The manuscript claims a uniform deterministic algorithm using a number of bit operations polynomial in ; the bound therefore accounts for the size of the prime, not just the polynomial degree.
The abstract identifies one central ingredient of the argument: the uniform Hecke zero-free theorem from the companion paper, *Primitive roots for every admissible integer base*. Thus the factorization manuscript depends on a result supplied by that companion manuscript. The supplied text does not explain the zero-free theorem's precise statement or how it is converted into the factorization algorithm, so a more detailed account of the argument is not available here. The claimed algorithm requires no randomness, integer-factorization oracle, primitive-root oracle, or GRH assumption.
Useful notions
- Arithmetic modulo a prime
- Polynomial degree and coefficient lists
- Irreducible factors and multiplicities
- Binary encoding and bit complexity
- Deterministic polynomial-time algorithms
What was known before / what is new
Before
The supplied source does not describe earlier factorization algorithms or give a historical account of the problem. It identifies the uniform Hecke zero-free theorem in the companion manuscript as the result on which the main argument relies.
New
The manuscript claims a uniform deterministic algorithm for complete factorization of every nonzero, densely represented polynomial over a prime field, including multiplicities. Its claimed bit complexity is polynomial in , with the prime supplied in binary. The claim explicitly avoids randomness, integer-factorization and primitive-root oracles, and any GRH assumption.
Limits and assumptions
The stated scope is nonzero polynomials over prime fields, represented by full coefficient lists, with the prime supplied in binary. The source makes no corresponding claim for other fields or other input representations. The argument relies on the companion manuscript's uniform Hecke zero-free theorem, whose statement and argument are not included in the supplied abstract. The main result is not formalized in Lean and has not been formally verified. No remaining open problems are specified in the source.
Mini glossary
- Prime field —
- Here, the field consists of numbers calculated modulo a prime .
- Dense coefficient list —
- A representation that lists the polynomial's coefficients, including zero coefficients, through its degree.
- Irreducible factor —
- A nonconstant polynomial factor that cannot be split into two factors of smaller positive degree over the same field.
- Multiplicity —
- The number of times a particular irreducible factor occurs in a factorization.
- Bit complexity —
- A measure of computation that counts operations on binary digits.
- Deterministic algorithm —
- A procedure that follows fixed instructions without making random choices.
Keywords : Polynomial factorization · Prime fields · Deterministic algorithms
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Gives a uniform deterministic algorithm that completely factors every nonzero dense degree-n polynomial over a prime field 𝔽p, including multiplicities, in bit complexity polynomial in . The prime is supplied in binary. No randomness, integer-factorization or primitive-root oracle, or GRH assumption is required.
To be verified: the proof is written in the manuscript, but no software has checked it and no validation by independent mathematicians is established. It may contain errors.
Manuscripts in this family
Deterministic Polynomial Factorization over Prime Fields
04/10/2026We give a uniform deterministic polynomial-time algorithm for complete factorization over prime fields. For a prime p in binary and a nonzero polynomial given by its dense coefficient list, the algorithm computes the irreducible factors and their multiplicities using a number of bit operations polynomial in . The proof uses the uniform Hecke zero-free theorem from the companion paper *Primitive roots for every admissible integer base*.