Alec Kriebel

Output-sensitive sparse factorization over finite fields from dense factorization

Read the paper (PDF) · Download PDF · Supporting ZIP · Zenodo record

Plain-English explanation · Read on this page · Collaboration


Abstract

We give a deterministic reduction for complete factorization of a sparse univariate polynomial over an explicitly represented finite field. Its cost is polynomial in the term count, binary exponent length, field encoding, and total degree of the distinct densely returned factors, including arbitrary binary multiplicities. The reduction maintains a sparse numerator and a dense denominator during characteristic-p descent. The numerator degree shrinks by p, while the denominator degree grows by at most the original radical degree per step. Classical logarithmic derivatives, Padé reconstruction, residue multiplicity arguments and Cartier sections supply the individual tools. We also detail the established dense factorization and irreducible construction reductions of Berlekamp and Shoup. Substitution of OpenAI's prime-field theorem gives uniform deterministic polynomial bit complexity, without GRH, randomness or an integer-factorization oracle. That input requires the companion general cyclotomic Hecke zero-free theorem; this paper neither reproves its breakthrough nor claims formal verification.

The idea in plain English

A polynomial can have only a few written terms while its exponents are enormous. Factoring it may still require a long answer. This note measures the work against both the short input and the size of the explicitly returned factors, keeping repeated-factor multiplicities in binary. The resulting deterministic complexity conclusion uses OpenAI's cited prime-field theorem and its general cyclotomic Hecke dependency, together with established finite-field reductions.

The precise result

For an explicitly represented finite field, the bit cost of completely factoring a sparse polynomial is polynomial in the term count, binary exponent length, field encoding and total degree of its distinct irreducible factors returned densely. Multiplicities are returned in binary. The dense and prescribed-degree irreducible construction consequences use their ordinary output sizes.

How the argument works

Characteristic-p descent shrinks the sparse numerator while controlling the degree of a dense denominator. Logarithmic derivatives and Padé reconstruction recover the relevant factor information. The cited prime-field result makes the final bit bound unconditional.

Scope

The output includes dense coefficients for every distinct factor. A bound in the size of a sparse factor list would be a different claim. Prescribed-degree irreducible construction is polynomial in the requested degree, and zero is excluded from complete factorization.

Background and prior work

OpenAI supplies the prime-field theorem used in Corollary 3. It depends on the OpenAI preprint. The finite-field steps use earlier reductions of E. R. Berlekamp, V. Shoup and S. S. Rai.

Status and AI use

Unrefereed preprint. AI tools assisted substantially in developing, writing and checking the work. Independent human review is welcome.

Read the paper

Open the published PDF · Download PDF · Original PDF on Zenodo

Supporting materials

Download verification.zip · Original verification.zip on Zenodo

Collaborate on this result

I welcome independent checks of the descent and the bit-complexity accounting in the stated output model.

Authorship and responsibilities would be discussed in relation to substantive contributions. Contact Alec.

Cite this paper

Kriebel, Alec (2026). Output-sensitive sparse factorization over finite fields from dense factorization. Zenodo. 10.5281/zenodo.23205034.

Download BibTeX

Licensing

The deposited work is available under Creative Commons Attribution 4.0.