O18a — Recognizing primitive roots deterministically

Definitions and mathematical statement

For a prime $p$, the group $\mathbb F_p^\times$ consists of the nonzero residues modulo $p$ under multiplication. It is cyclic of order $p-1$. A residue $b$ is a primitive root if its powers exhaust this group, or equivalently if its multiplicative order is exactly $p-1$.

Given $p$ in binary and a residue $b\in\{0,\ldots,p-1\}$, can one decide deterministically, in time polynomial in $\log p$, whether $b$ is a primitive root? The answer for $b=0$ is negative; when $p=2$, the element $1$ generates the trivial unit group and is accepted. The primality of $p$ is an input promise.

An equivalent criterion for nonzero $b$ is \[ b^{(p-1)/q}\not\equiv1\pmod p \quad\text{for every prime }q\mid(p-1). \] This criterion specifies exactly the required property, but the distinct prime divisors of $p-1$ are not supplied as additional input. An algorithm that uses their factorization must include the cost of obtaining it.

The output is only a decision bit. Constructing a generator or computing the complete multiplicative order is not demanded. The proposed algorithm must have one unconditional polynomial bound covering every prime, including those for which $p-1$ has large prime factors. Random sampling, nonuniform precomputed tables, or successful verification of some specially chosen primes does not supply the universal deterministic decision procedure requested.

Short English statement

Can primitive roots modulo a given prime be recognized deterministically in polynomial bit complexity?

Sources

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