Primitive Roots

Cryptography · Axiom Academy

Generators of multiplicative groups and their role in Diffie-Hellman key exchange The order of an element a modulo n is the smallest positive integer k such that a k ≡ 1 (mod n). An element g is a primitive root modulo n if its order equals φ(n), where φ is Euler's totient function. 3. Which n Have Primitive Roots? Not all moduli have primitive roots. Primitive roots exist only for specific values of n. 4. Finding and Counting Primitive Roots When primitive roots exist for n, there are exactly φ(φ(n)) of them. 5. Primitive Roots in Diffie-Hellman Primitive roots are essential for the Diffie-Hellman key exchange protocol and the discrete logarithm problem.

This is the written version of the interactive lesson above. See the full Cryptography course.