Deterministic polynomial factorisation modulo many primes

2025/09/16 by Daniel Altman, Altman, Daniel
Computer Science · Mathematics · #11T06 #11Y05 #11Y16 #68W30 #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Number Theory (math.NT) #Rings, Modules, and Algebras

paper · pdf · doi:10.48550/arxiv.2509.12705

openalex publication_date 2025/09/16 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28

Abstract

Designing a deterministic polynomial time algorithm for factoring univariate polynomials over finite fields remains a notorious open problem. In this paper, we present an unconditional deterministic algorithm that takes as input an irreducible polynomial f ∈ ℤ[x], and computes the factorisation of its reductions modulo p for all primes p up to a prescribed bound N. The average running time per prime is polynomial in the size of the input and the degree of the splitting field of f over ℚ. In particular, if f is Galois, we succeed in factoring in (amortised) deterministic polynomial time.

Citations

• Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach
• Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields
• Character Sums and Deterministic Polynomial Root Finding in Finite Fields
• Factoring polynomials with rational coefficients

Related

• Schemes for Deterministic Polynomial Factoring
• Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
• A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
• Efficiently factoring polynomials modulo p⁴
• Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields