Skip to content

Primitive Root Hot Sheet

Use this page when the task is:

given prime p, output one primitive root modulo p

and you want the shortest safe route back to the generator test.

Do Not Use When

  • the unknown is in the exponent rather than the base
  • the exact task is only x^2 ≡ a (mod p)
  • the modulus is composite and you have not separated that case
  • factoring p - 1 is the real bottleneck and this starter contract is too narrow

Choose By Signal

Core Invariants

  • for prime p, the nonzero residues form a cyclic group of size p - 1
  • candidate g is primitive iff:
\[ g^{(p-1)/q} \not\equiv 1 \pmod p \]

for every distinct prime divisor q of p - 1

  • p = 2 is the trivial edge case with answer 1
  • the first route is only as good as your access to the distinct prime divisors of p - 1

Main Traps

  • forgetting to deduplicate prime divisors of p - 1
  • testing the prime-mod criterion unchanged under composite moduli
  • forgetting the p = 2 edge case
  • using trial division when the true bottleneck is 64-bit factorization of p - 1

Exact Starters In This Repo

Reopen Paths