O22a — Discrete logarithms modulo a composite

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Integers are supplied in binary; polynomial time means a polynomial number of classical bit operations in total input length. Given positive integers $g,b,n$ with $n\ge2$, seek a positive integer exponent $x$ satisfying $g^x\equiv b\pmod n$. The computational question is a search problem promised a solution; no coprimality assumption on $g$ is imposed in C22.

Statement recorded in the supplied source.

Is there a deterministic polynomial-time algorithm which produces such an $x$ on every input for which a solution exists? [S2]

Short English statement

Can a modular discrete logarithm be found deterministically in polynomial time for an arbitrary modulus, including composites, whenever it exists?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8400025 (AMR-083-0025). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Leonard M. Adleman and Kevin S. McCurley, Open Problems in Number Theory Complexity, II, in Algorithmic Number Theory, LNCS 877 (1994), pp. 291--322, C22/O22a, manuscript p. 17 (LNCS p. 307), and Definition 2. https://mccurley.org/papers/open.ps.gz.