O20 — Computing multiplicative orders modulo a prime

Definitions and mathematical statement

Let $p$ be a prime and $a\in\{1,\ldots,p-1\}$. The multiplicative order of $a$ modulo $p$ is \[ \operatorname{ord}_p(a)=\min\{t\ge1:a^t\equiv1\pmod p\}. \] It exists and divides $p-1$, since $a$ belongs to the finite group $\mathbb F_p^\times$. In particular, $\operatorname{ord}_p(1)=1$, including when $p=2$.

Can the exact integer $\operatorname{ord}_p(a)$ be computed by a deterministic classical algorithm in time polynomial in the combined binary lengths of $p$ and $a$? The inputs are promised to have $p$ prime and $a$ nonzero modulo $p$. They do not include a factorization of $p-1$ or of the unknown order.

The output must be the least positive exponent yielding one, rather than an arbitrary multiple of that exponent. The universal exponent $p-1$, although quickly available, therefore does not generally answer the question. Likewise, testing a single asserted exponent by modular powering does not prove it is the minimum.

One uniform algorithm and one polynomial time bound must work for every input pair. Any integer factorizations, auxiliary searches, or preprocessing used by the algorithm count towards its cost. The intended computation is classical and deterministic, with no oracle and no unproved number-theoretic assumption. Producing the order in binary is sufficient; constructing the complete subgroup or listing its elements is unnecessary.

Short English statement

Can exact multiplicative orders modulo primes be computed deterministically in polynomial time?

Sources

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