O7a — Computing the squarefree part

Definitions and mathematical statement

A positive integer $s$ is squarefree when no square of a prime divides $s$; in particular, $1$ is squarefree. Every $N\ge1$ has a unique expression \[ N=r^2s,\qquad r,s\in\mathbb N,\quad s\text{ squarefree}. \] If $N=\prod_p p^{e_p}$, then $r=\prod_p p^{\lfloor e_p/2\rfloor}$ and $s=\prod_{e_p\text{ odd}}p$. The integer $s$ is the squarefree part in this problem. It is not in general the radical $\prod_{e_p>0}p$: for example, $12=2^2\cdot3$ has squarefree part $3$ and radical $6$.

Does there exist a deterministic classical algorithm which, given $N$ in binary, outputs the pair $(r,s)$ in a number of bit operations bounded by a fixed polynomial in the binary length of $N$? Requiring only $s$ is equivalent, since $r$ is the exact positive square root of $N/s$ and can then be computed efficiently.

The algorithm must work for every positive integer, without receiving a prime factorization and without random choices. The displayed formula in terms of prime exponents defines the desired result, but is not an efficient construction unless those exponents can themselves be obtained within the bound. The target is extraction of all square factors, including those arising from large repeated prime divisors.

Short English statement

Can the unique squarefree part of an integer be computed deterministically in polynomial bit complexity?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 8400007 (AMR-083-0007), 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), O7a, p9 / LNCS p299. Original source indexed by AMR-083-0007. https://mccurley.org/papers/open.ps.gz.