Irreducibility testing for sparse integer polynomials is computationally hard

Irreducibility Testing of Sparse Polynomials over Integers is NP-hard and Probabilistic Polynomial Time

Computational Complexity

Summary

This paper shows that deciding whether a certain type of polynomial, called a sparse polynomial with integer coefficients, cannot be broken down into simpler polynomials is very hard from a computational viewpoint. The authors prove that there is likely no fast, guaranteed method to test for this property unless a major open problem in computer science is solved. However, they also demonstrate that the problem can be tackled using methods that run in reasonable time on average with some probability of error, and with controlled memory usage. Their results rely on advanced mathematical hypotheses and recent number theory breakthroughs.

What this means in practice

  • For cryptographic engineers: Understand the computational limits of testing polynomial irreducibility that affect constructing cryptographic primitives relying on hardness assumptions.
  • For computer algebra system developers: Implement probabilistic algorithms for irreducibility testing that run efficiently within polynomial space for sparse polynomials over integers.

A theory result. No direct application yet.

Authors

Yichuan Cao, Xiao-Shan Gao, Qiao-Long Huang, Jiawei Nie

Abstract

In this paper, we prove that irreducibility testing for sparse polynomials in $\mathbb{Z}[X]$ is coNP-hard under deterministic polynomial-time many-one reductions. That is, there exists no polynomial-time irreducibility test algorithm unless $\mathrm P=\mathrm{NP}$. We also provide an upper bound for this problem by demonstrating that the same irreducibility testing problem lies in $\mathsf{PP}\subseteq\mathsf{PSPACE}$; in other words, it can be solved in probabilistic polynomial time and, moreover, within polynomial space. The fact that $\mathsf{SparseIrred}_{\mathbb{Z}}\in\mathsf{PP}$ relies on the quasi-Riemann hypothesis result of Cureton--Thorner and on the uniform effective prime-ideal bound by Frei--Sofos--Widmer just posted recently.
View PDFOpen arXiv