Deterministic polynomial factorization over prime fields

The explanation

Work with whole numbers modulo 5, where only the remainders 0 to 4 count. Take the polynomial x² + 1. Put in x = 2, and you get 5, which counts as 0. Put in x = 3, and you get 10, also 0. So x² + 1 splits as (x − 2)(x − 3). Check it: the product is x² − 5x + 6, and modulo 5 that is x² + 1. Now work modulo 7 instead. The squares there are only 1, 2 and 4, so x² + 1 is never 0. Modulo 7, the same polynomial cannot be split at all.

This is factorization over a prime field. A prime field is the arithmetic of remainders after division by a prime p. Complete factorization means writing a polynomial as a constant times irreducible pieces, each with its multiplicity. An irreducible piece is one that cannot be split further. The multiplicity counts how often a piece repeats.

The difficulty is the size of p. The input gives p by its binary digits. A prime near 10¹⁰⁰ needs only 333 binary digits, but trying every remainder means 10¹⁰⁰ trials. So an efficient method must run in time polynomial in the number of digits, not in p itself. The paper also asks for polynomial time in the degree n at the same time.

Random guessing solves this efficiently. Berlekamp's work in 1967 and 1970 used linear algebra to reduce factoring to finding suitable separating elements. Cantor and Zassenhaus in 1981 found such elements by random choices, in expected polynomial time. The hard part is making every choice without randomnessSource 1. Shoup's 1990 method avoids randomness, but its time grows roughly like the square root of p. For p near 10¹⁰⁰, the square root is 10⁵⁰. Other results assumed the generalized Riemann hypothesis, or GRH, an unproven conjecture about the zeros of certain functions. Under GRH, Evdokimov in 1994 reached a quasipolynomial bound in n, a little worse than any fixed power of n.

The paper claims a deterministic method, one that never flips a coin, for every prime and every degree. Its running time is at most a constant times ((n + 1) times the number of binary digits of p) to the power 10¹²Source 2. The exponent is deliberately generous. The point is one fixed polynomial bound for all degrees and all primesSource 3. The method uses no randomness, no help factoring integers, and no GRHSource 4.

The method first reduces the job to one case. The polynomial has distinct roots, and every root is already one of the remaindersSource 5. When the number of roots is even, a tournament trick worksSource 6. Compare every pair of roots by a fixed rule, so one of each pair wins. With 4 roots there are 6 games in all. Equal scores would need 1.5 wins each, which is impossible. So unequal scores separate the roots into groups. When the number of roots is odd, the paper uses an auxiliary curve, the solutions of an equation built from the polynomialSource 7. It shows that certain labels on that curve cannot all agreeSource 8. Different labels then split the polynomial.

Both cases need extra arithmetic information, prepared without guessing. The paper gets it from auxiliary primes. These are small primes with a special relation to p. Showing that small enough ones always exist needs a zero-free theorem for Hecke L-functions. These are functions built from primes, and their zeros control how primes are spread. This paper takes that theorem as an input. It comes from the companion paper “Primitive roots for every admissible integer base”Source 9. The algebraic reduction itself does not use itSource 10.

How sure is this? No Lean formalization is listed for this result in the openai/math release. So no computer proof checker has checked it. The polynomial-time claim also depends on the companion paper's analytic theorem, which is itself unreviewed. No specialist review of either paper has been published.

What it doesn't show. This does not give a fast practical method: the claimed bound has exponent 10¹², which the paper calls deliberately generous.