Skip to content

Primitive Root Ladder

Who This Is For

Use this lane when modular arithmetic basics feel comfortable, but "find a generator modulo p" still feels like abstract group theory instead of one reusable contest test.

Warm-Up

  • fast power under modulo
  • factorization of p - 1
  • order of an element modulo one prime
  • why the nonzero residues modulo p form one cyclic group

Core

  • prime-mod generator finding through order tests
  • factor p - 1 into its distinct prime divisors
  • reject a candidate g if one power:
\[ g^{(p-1)/q} \]

collapses to 1 - flagship verifier-style rep: Primitive Root

Stretch

  • explain why this lane is about generators, not exponent recovery
  • compare primitive-root finding with BSGS / Discrete Log
  • compare the primitive-root doorway with the Tonelli-Shanks starter lane in Modular Square Root / Discrete Root
  • say when factorization of p - 1 becomes the real bottleneck instead of the generator test

Retrieval Layer

Repo Anchors

Exit Criteria

You are ready to move on when you can:

  • state the exact prime-divisor test for one candidate generator
  • explain why checking the distinct prime divisors of p - 1 is enough
  • distinguish generator finding from discrete log and modular square-root extraction
  • say when the factorization layer, not the order test, becomes the limiting step

External Practice