O8 — Deterministic polynomial-time squarefreeness testing

Definitions and mathematical statement

A positive integer $N$ is squarefree if there is no prime $p$ for which $p^2\mid N$. Equivalently, in its unique prime factorization every exponent is either zero or one. The integer $1$ is squarefree. For example, $30$ is squarefree, while $12$ is not because $2^2$ divides it.

The input is the binary expansion of an arbitrary positive integer $N$. The output is a single bit, equal to one precisely when $N$ is squarefree. Is there a deterministic classical algorithm which always returns the correct bit using at most $C(1+\ell(N))^c$ bit operations, for some absolute constants $C,c>0$, where $\ell(N)$ denotes binary length?

No prime factorization or bound on the prime divisors is provided as part of the input. The requirement is a worst-case guarantee for every positive integer. Trial division by every prime up to $\sqrt N$ decides the property, but does not supply the polynomial bound in binary length sought here.

The task is solely a decision problem: on a negative instance an algorithm need not output a prime whose square divides $N$, and on a positive instance it need not list all prime divisors. Likewise, computing the full squarefree part would suffice to decide squarefreeness, but is a stronger output requirement. An answer must therefore address this exact yes-or-no task in the classical deterministic bit model.

Short English statement

Can squarefree integers be recognized deterministically in time polynomial in their binary length?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400009 (AMR-083-0009), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Adleman & McCurley - Open Problems in Number Theory Complexity II (1994), O8, p9 / LNCS p299. Original source indexed by AMR-083-0009. https://mccurley.org/papers/open.ps.gz.