O18b — Recognizing primitive roots randomly

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. On promised inputs $b\in\mathbb N$ and a prime $p$, call $b$ a primitive root modulo $p$ if its residue generates $(\mathbb Z/p\mathbb Z)^\times$. The source's notion of recognition in $R$ means one-sided randomized acceptance: positive instances are accepted with probability at least $1/2$, negative instances are never accepted, and other outcomes are designated $?$.

Statement recorded in the supplied source.

Can primitive roots modulo a prime be recognized in $R$ in this sense, without receiving the factorization of $p-1$? [S2]

Short English statement

Is there a polynomial-time randomized procedure which can certify primitive-root instances with bounded success probability and never falsely certify a non-generator?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8400021 (AMR-083-0021). 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, C18/O18b, manuscript p. 14 (LNCS p. 304), and Definition 5. https://mccurley.org/papers/open.ps.gz.