O7b — Factoring from a squarefree-part oracle

Definitions and mathematical statement

Define the squarefree-part function $\operatorname{sf}(N)$ for positive integers by the unique decomposition \[ N=r^2\operatorname{sf}(N),\qquad r\in\mathbb N, \] where $\operatorname{sf}(N)$ has no repeated prime divisor. Thus $\operatorname{sf}(N)$ retains precisely those prime factors whose exponents in $N$ are odd. Consider an exact oracle which, on a positive binary integer $u$, returns $\operatorname{sf}(u)$ in binary.

Can complete integer factorization be reduced to this oracle by a classical randomized polynomial-time algorithm? More explicitly, is there one probabilistic oracle machine which, on every $N\ge2$, outputs all prime factors of $N$ with their multiplicities with probability at least $2/3$, using polynomially many ordinary bit operations and oracle calls, all queries having binary length polynomial in $\ell(N)$? Queries may be adaptive and may involve integers other than $N$.

The oracle supplies only squarefree parts, not factorizations of those parts. For squarefree $N$ its direct answer is simply $N$, so the problem concerns whether auxiliary queries can reveal the missing factors. Running time includes constructing queries and reading answers, but not the internal work of the oracle. Correct factorization outputs are efficiently verifiable, allowing the equivalent expected-polynomial, always-correct formulation by verification and repetition. The question is a reduction between exact computational tasks, and does not assume either task already has an efficient ordinary algorithm.

Short English statement

Does an exact squarefree-part oracle suffice for randomized polynomial-time complete integer factorization?

Sources

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