O21 — Discrete logarithms modulo a prime

Definitions and mathematical statement

Let $p$ be a prime and let $g,b\in\mathbb F_p^\times$. Write $\langle g\rangle=\{g^j:j\in\mathbb Z\}$ for the cyclic subgroup generated by $g$. The input is promised to satisfy $b\in\langle g\rangle$. A discrete logarithm of $b$ to base $g$ is an integer $x$ with \[ g^x=b\quad\text{in }\mathbb F_p^\times. \] Its residue class is unique modulo $\operatorname{ord}_p(g)$, although a representative need not be unique as an ordinary integer.

Is there a deterministic classical algorithm that, on every such binary input $(p,g,b)$, outputs a nonnegative exponent $x<p$ satisfying this equality in time polynomial in the input length? Allowing another polynomial-length representative gives the same search problem after reduction modulo $p-1$.

The base need not generate all of $\mathbb F_p^\times$. Neither its order nor a factorization of $p-1$ is supplied, and all auxiliary work is counted. When $g=1$, the promise forces $b=1$, so $x=0$ is a valid answer.

The question concerns exact logarithms on every valid instance; it does not ask for a real logarithm, an approximation, or a result averaged over random primes and residues. The bound is polynomial in binary length, not in the group order. The computational model is classical, so a quantum algorithm does not meet the stated requirement.

Short English statement

Can discrete logarithms in subgroups of prime-field multiplicative groups be computed deterministically in polynomial time?

Sources

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