O11b — Factoring from composite quadratic residuosity

Definitions and mathematical statement

A quadratic-residuosity oracle accepts a composite integer $m\ge4$ and a residue $a$ with $\gcd(a,m)=1$. It returns one if $a\equiv x^2\pmod m$ for some integer $x$, and zero otherwise. It returns no square root, no prime divisor, and no information about how many roots exist. All integers are encoded in binary.

Is there a classical randomized polynomial-time reduction from complete integer factorization to this decision oracle? Precisely, seek a uniform probabilistic algorithm which, on every $N\ge2$, outputs the distinct prime factors of $N$ and their positive multiplicities with success probability at least $2/3$. Its ordinary computation, number of oracle calls, and lengths of all oracle queries must be bounded by fixed polynomials in the binary length of $N$.

The algorithm may choose its queries adaptively and may use composite moduli different from the integer being factored. Queries outside the specified domain cannot supply trusted information; prime-modulus residuosity can be decided by ordinary modular exponentiation. Costs of forming queries and reading replies count as ordinary computation.

This asks whether existence information about modular square roots is sufficiently informative to recover prime factors. An oracle that actually returns roots is stronger and is not interchangeable with the decision oracle by definition. Correct factorization outputs can be checked, so constant-probability success may equivalently be converted to an always-correct expected-polynomial algorithm.

Short English statement

Can complete factorization be performed in randomized polynomial time using only a quadratic-residuosity decision oracle?

Sources

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