Primitive Root Finder

g generates (Z/nZ)*

CalculatorsFreeNo Signup
4.5(502 reviews)
All Tools

Loading tool...

About Primitive Root Finder

A primitive root finder computing generators g of (Z/nZ)* where ord(g) = φ(n). Shows all primitive roots, verifies order, and lists powers of g. Primitive roots exist iff n = 1,2,4,pᵏ,2pᵏ. All calculations are client-side.

Primitive Root Finder Features

  • Find roots
  • All roots
  • Verify order
  • Power table
  • Existence check
Primitive root g mod n: ord(g) = φ(n), meaning g generates (Z/nZ)*. Exists iff n = 1,2,4,pᵏ,2pᵏ (p odd prime). Count: φ(φ(n)) primitive roots. Smallest primitive root mod p is O(p^(1/4+ε)) (under GRH).

How to Use

Enter n:

  • Exists?: Check if primitive roots exist
  • Smallest: Find smallest primitive root
  • All: List all primitive roots

Existence

Primitive roots exist mod n iff n = 1, 2, 4, pᵏ, or 2pᵏ (p odd prime, k≥1). For n=8,12,15,... no primitive root exists because (Z/nZ)* is not cyclic.

Applications

  • Diffie-Hellman key exchange
  • ElGamal encryption
  • Discrete logarithm
  • Number-theoretic transforms

Step-by-Step Instructions

  1. 1Enter n.
  2. 2Check existence.
  3. 3Find smallest root.
  4. 4View all roots.
  5. 5See power table.

Primitive Root Finder — Frequently Asked Questions

How to find a primitive root?+

For prime p: test g=2,3,5,... Check if g^((p−1)/q) ≢ 1 (mod p) for each prime factor q of p−1. If all pass, g is a primitive root. The smallest is usually very small (often < 100 even for large primes).

Why do primitive roots matter in cryptography?+

Diffie-Hellman and ElGamal rely on the discrete log problem in cyclic groups. A primitive root g mod p generates the full group, making discrete log as hard as possible. Without a primitive root, the group would decompose into smaller, easier subproblems.

How many primitive roots exist mod p?+

Exactly φ(p−1) primitive roots mod prime p. If g is one, all others are g^k where gcd(k,p−1)=1. For p=7: φ(6)=2 roots (3 and 5). For p=11: φ(10)=4 roots (2,6,7,8).

More Calculators Tools

Explore all 639 other calculators tools available on Generatr

1-Sample Z-Test Calculator2-Sample Z-Test Calculator3D Surface Area CalculatorA/B Testing Significance CalculatorAbsolute Value CalculatorAbundant Number CheckerAccelerated Aging CalculatorAchromatic Number CalculatorAcyclic Chromatic Number CalculatorAdditive Persistence CalculatorAge CalculatorAging Test CalculatorAlbertson Index CalculatorAlgebraic Connectivity CalculatorAliquot Sequence CalculatorAliquot Sum CalculatorAlternating Series Test CalculatorAmicable Number FinderAnnuity CalculatorAPY CalculatorAquarium CO2 Drop CheckerArea CalculatorArea Under Curve CalculatorArithmetic Sequence CalculatorArmstrong Number CalculatorASCVD Risk CalculatorAspect Ratio CalculatorAtom Bond Connectivity CalculatorAugmented Eccentric Connectivity CalculatorAugmented Zagreb Index Calculator
View all 639 calculators tools
Share this tool: