O22b — Factoring from composite discrete logarithms

Definitions and mathematical statement

For a modulus $m\ge2$, a modular discrete-logarithm oracle receives positive integers $g,b$ and, whenever possible, returns an integer $x$ with $1\le x\le m$ satisfying $g^x\equiv b\pmod m$. The input residues need not be units, and the source problem allows arbitrary moduli, including primes. If a solution exists, a representative $1\le x\le m$ exists, by eventual periodicity of the sequence of powers in the finite residue ring.

Is complete integer factorization deterministically polynomial-time reducible to this search problem? The required reduction is one deterministic classical oracle algorithm which, on every binary input $N\ge2$, returns all distinct prime factors and their multiplicities. Its ordinary bit operations, number of queries, and query lengths must be bounded by fixed polynomials in the binary length of $N$.

Queries may be adaptive and may use moduli different from $N$. On solvable queries the oracle may choose any correct logarithm; the reduction cannot require a special canonical choice. On unsolvable queries its behavior is unrestricted, including giving no response. The source permits interleaving subroutine calls, and the reduction must work for every oracle consistent with the promised outputs.

Oracle internal running time is excluded from the reduction's cost, while constructing queries and processing replies are counted. No factorization of a query modulus is supplied automatically. Randomized reductions do not meet the deterministic target in this question.

Short English statement

Can arbitrary integers be factored deterministically in polynomial time with a modular discrete-logarithm oracle?

Sources

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