Episode 142, October 2026

Factoring with no coin flips?

A claimed deterministic algorithm that completely factors every polynomial over a prime field, with one polynomial bound for all degrees and all primes

Covers result 142 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 142: Factoring with no coin flips? A crossed-out coin above a factor tree whose leaves are roots.

7:33. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

x⁴ + 1 cannot be factored over the integers, yet modulo every prime it breaks apart: modulo 13 into (x² + 5)(x² − 5), modulo 17 into four linear factors. Factoring over the integers modulo a prime p means finding the irreducible pieces and how often each repeats. The input is the list of coefficients and p written in binary, so its size is about the degree times the number of digits of p, and a method whose cost grows like p is far too slow for a large prime.

As the paper recounts the history, Berlekamp put linear algebra at the center: elements fixed by the p-th power map encode the factors, and greatest common divisors pull them out. Randomized methods, including Cantor and Zassenhaus’s, make factoring fast with coin flips. Deterministically, Shoup’s bound grows like the square root of p; under the generalized Riemann hypothesis, Rónyai gave polynomial bounds for a bounded number of factors and Evdokimov a bound quasi-polynomial in the degree. Even taking square roots modulo p by the standard methods needs a non-square to start from, and a bound on the least non-square growing like a power of log p was known only under that hypothesis, until release result 3 claimed one. The paper itself does not call deterministic polynomial-time factoring an open problem, though the literature has long treated it as one.

Result 142 is one OpenAI preprint (48 pages, October 4, 2026). Theorem 1.1 claims a uniform deterministic algorithm that, given a prime p in binary and a nonzero polynomial f over 𝔽_p of degree n, outputs its leading coefficient and its distinct monic irreducible factors with their multiplicities in O(((n + 1)⌈log₂ p⌉)^10¹²) bit operations, using no randomness, no integer-factorization oracle, no primitive-root oracle and no generalized Riemann hypothesis. The paper calls the exponent “deliberately generous”; the proof gives O(B^400,000,100) with B = 20 + (n + 1)(L + 1) and L the bit length of p.

What it doesn’t claim

A practical algorithm. When p ≤ B²⁰⁰⁰⁰⁰ the algorithm runs Berlekamp’s method and tries field elements one by one, which counts as polynomial only because that cutoff is a fixed power of the input size; by our arithmetic, for a quadratic the other branch starts only at primes of about 1.43 million digits. Randomized methods remain the practical choice. The paper produces no primitive roots and states its result only for prime fields. Splitting an even number of roots given a non-square goes back to Rónyai (1988); the paper calls the odd-degree separator, with the divisions it needs, its substantive step.

The unconditional bound depends on another release result. Theorem 1.2, the core reduction, runs in time polynomial in the input and in supplied auxiliary primes ℓ (with ℓ ≡ 1 mod 12q and p not a q-th power modulo ℓ); under the generalized Riemann hypothesis this alone gives polynomial time. To find small auxiliary primes without that hypothesis, the paper imports from result 29 (our episode 29) a zero-free strip, Re s > 1 − 10⁻⁶, for every finite-order Hecke L-function of every cyclotomic field containing the twelfth roots of unity, and proves that an auxiliary prime exists below c₀B^20,000,000.

Where it stands

Posted as a preprint: OpenAI, 48 pages, dated October 4, 2026
Peer reviewed: Not yet
Checked in Lean: No, and neither is the zero-free strip it borrows from result 29

Last checked October 19, 2026. The preprint has not been revised. It is not formalized in Lean, we found no Lean files for this result in the repository, and result 29’s zero-free strip is not formalized either. Theorem 1.1 is proved only if result 29’s analytic theorem is; the reduction and the version under the generalized Riemann hypothesis do not depend on it. Neither paper is among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

Unknown roots. Strip repeated factors with the derivative and greatest common divisors. Berlekamp’s algebra then reduces everything to splitting a polynomial F with distinct roots, all in 𝔽_p, none of them known. Computing in 𝔽_p[T]/F works at all roots at once, and any test whose answer differs between two roots yields a factor by a greatest common divisor.
Even degree: a tournament. Given a generator of the 2-power part of the multiplicative group, each pair of roots is compared through one binary digit of a discrete logarithm of their difference; reversing the pair flips the digit, so exactly one direction of each pair is chosen. If every root won equally often, each would win (N − 1)/2 times, impossible for even N. The win counts are traces, computed without knowing any root.
Auxiliary primes. From a prime ℓ ≡ 1 mod 12q, modulo which p is not a q-th power, linear algebra in 𝔽_p[T]/(1 + T + ⋯ + T^ℓ−1) builds the generators the splitters need, in increasing order of q, without factoring p − 1.
Odd degree: a curve. For an odd prime q dividing the number of roots, the curve y^q = F(x) meets the x-axis once at each unknown root. With σ multiplying y by a q-th root of unity, the classes of those points are divided by 1 − σ again and again, summed over the roots, and read off as labels modulo q at each root. If the labels always agreed, a fixed divisor at infinity would be divisible by one more power of 1 − σ than it is, so some label separates the roots.
Making division an algorithm. Each division reduces to a norm equation, solved with explicit maximal orders, Grothendieck’s splitting of vector bundles on the projective line, and a rank-one idempotent found by linear algebra.
The analytic input. Everything is polynomial in the input and in the auxiliary primes; result 29’s strip guarantees one below c₀B^20,000,000, found by searching upward.

The numbers in the video

x⁴ + 1 is (x² + 5)(x² − 5) modulo 13, (x + 2)(x − 2)(x + 8)(x − 8) modulo 17 and (x + 1)⁴ modulo 2. Modulo 7, x⁸ + 3x⁷ − 2x⁶ − 2x³ + 3x² + x = x(x + 1)³(x² + 1)².
For (x − 3)(x − 50) modulo 101, the greatest common divisor with (x + a)⁵⁰ − 1 is 1 at a = 0 and x − 3 at a = 1.
Over all 664,577 primes from 5 to ten million, the least non-square averages 3.66 and is at most 53 (at p = 9,257,329).
The even-degree tournament, run blind modulo 10,009 on eight roots: win counts 3, 7, 2, 1, 3, 3, 5 and 4, and the factor x + 2046 (the root 7,963) split off.
A separate example of the q = 2 table entry: p = 10,009 and ℓ = 313 give a fixed field of dimension 2 inside a space of dimension 312 and the non-square 7,585.
For q = 3 and nine roots, the divisor at infinity (−9, 9, 0) divides by 1 − σ exactly four times, ending at (0, −1, 1).
Least auxiliary primes for a 100-digit prime: 73, 37 and 61 for q = 2, 3 and 5; none above 1,201 in all our checks, against the proved c₀B^20,000,000.

Read the source

Deterministic Polynomial Factorization over Prime Fields (PDF), 48 pages.
Primitive roots for every admissible integer base (PDF), the companion that supplies the zero-free strip (result 29).
The collection’s catalog, where this is result 142.

The paper

OpenAI groups related papers into one result; this one has a single paper.

Deterministic Polynomial Factorization over Prime Fields

Transcript

Read the full script

0:00Breaking a polynomial apart

Take the polynomial x⁴ + 1. Over the integers it cannot be factored, but modulo every prime it breaks apart: modulo 13 into two quadratics, and modulo 17 into four linear factors. Factoring over the integers modulo a prime p means finding the irreducible pieces and how often each repeats. Modulo 7, one polynomial of degree 8 is x · (x + 1)³ · (x² + 1)². This is a basic task in computer algebra. The size of the input is about the degree times the number of digits of p, so an algorithm that takes about p steps is hopeless for a large prime. Berlekamp, in the late 1960s, put linear algebra at the center: elements fixed by the p-th power map encode the factors. Randomized methods, such as Cantor and Zassenhaus’s, made it fast with coin flips: a random shift a separates two given roots about half the time, through a greatest common divisor with (x + a)^((p − 1)/2) − 1. For (x − 3)(x − 50), modulo 101, a = 0 fails, and a = 1 splits off x − 3. Trying a = 0, 1, 2 in order almost always works quickly, but no one could prove that a short search always succeeds. Even the standard methods for square roots modulo p need a non-square to start from. Below ten million the least one is never more than 53, but a bound growing like a power of the number of digits of p was known only under the generalized Riemann hypothesis, before result 3 of this release claimed one. As the paper recounts, earlier deterministic bounds grew like the square root of p, due to Shoup, or, under that hypothesis, quasi-polynomially in the degree, due to Evdokimov.

1:53The claim

Result 142 is a single OpenAI preprint, 48 pages, dated October 4. It claims one deterministic algorithm that completely factors every nonzero polynomial over the integers modulo a prime, with multiplicities, for every degree and every prime given in binary. Its cost is at most a constant times the input size to the power 10^12, in bit operations, with no randomness, no integer-factoring oracle, no supplied primitive root, and no generalized Riemann hypothesis. The paper calls that exponent deliberately generous; the proof gives about 400 million. Its core is a reduction: given small auxiliary primes, the algorithm runs in time polynomial in the input and in those primes, and under the generalized Riemann hypothesis this reduction alone already gives polynomial time. That is polynomial in principle, not fast. Below an astronomically large cutoff, it simply runs Berlekamp’s method and tries field elements one by one, which counts as polynomial only because the cutoff is a fixed power of the input size. By our arithmetic, for a quadratic, the other branch starts only at primes of about 1.4 million digits. Randomized methods remain the practical choice. The unconditional bound rests on result 29, which claims a zero-free strip of width one millionth for every finite-order Hecke L-function of every cyclotomic field containing the twelfth roots of unity; that paper is unreviewed, with no Lean proof. Splitting an even number of roots, given a non-square, goes back to Rónyai in 1988; the paper calls the odd-degree separator its substantive step. It does not produce primitive roots, and the paper states it only for prime fields. The paper does not call the problem open, though the literature has long treated it as one.

3:53How the proof goes

The proof first strips repeated factors, using the derivative and greatest common divisors. Berlekamp’s algebra then reduces everything to one task: split a polynomial with distinct roots, all of which lie in the field, but none of which is known. To compute with unknown roots, compute at all of them at once, in the ring of remainders modulo the polynomial. Any test whose answer differs between two roots shows up there, and a greatest common divisor then splits the polynomial. So the goal becomes: find a question the roots cannot all answer the same way. For an even number of roots, the paper uses a tournament. Given a generator of the part of the multiplicative group whose order is a power of two, each pair of roots is compared through one binary digit of a discrete logarithm of their difference, a digit that flips when the pair is reversed, so exactly one direction of each pair is chosen. With n roots, if every root won equally often, each would win (n − 1)/2 times, which is impossible when n is even, and the win counts are computed by traces without knowing any root. In our run modulo 10,009, eight roots won between 1 and 7 times, and the algorithm split off one root. The generators come from auxiliary primes ℓ, one more than a multiple of 12q, modulo which p is not a q-th power; linear algebra in the cyclotomic ring of order ℓ builds them. For p = 10,009 and ℓ = 313, it produced the non-square 7,585. For an odd number of roots, take an odd prime q dividing it, and the curve y^q equals the polynomial, which meets the x-axis once at each unknown root. Multiplying y by a q-th root of unity is a symmetry, sigma. The paper repeatedly divides classes of those points by one minus sigma, adds them up over all roots, and reads off a label at each root. If every label always agreed, a fixed divisor at infinity would become divisible by one more power of one minus sigma than it can be; in our toy with q = 3 and nine roots, it divides exactly four times and then stops. Each division means solving a norm equation, by explicit maximal orders and linear algebra. All of this is polynomial in the input size and in the auxiliary primes themselves, and through result 29’s strip the paper proves one exists below a constant times the input size to the power 20 million, found by searching upward. In our checks the least ones were tiny: 73, 37 and 61 for a hundred-digit prime, and none above 1,201.

6:41Where it stands

The preprint is not peer reviewed and has not been revised. It is not formalized in Lean, and neither is the zero-free strip it borrows. It is not among those OSVerify reviewed, and we have seen no expert review. The unconditional theorem is proved only if result 29’s analytic theorem is; the reduction itself, and the version under the generalized Riemann hypothesis, which would already improve on Evdokimov’s bound, do not depend on it. If it holds, every polynomial over a prime field can be completely factored by one deterministic procedure, with a single polynomial bound for all degrees and all primes, and no coin flips. The bound is astronomically large, so randomized algorithms stay in use; what changes is what is proved, not what is practical.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.