gen-state-primitive-roots-precisely-and-explain-why-it-matters-i-f23b

State primitive roots precisely and explain why it matters in 2-3 sentences.

## Primitive Roots A **primitive root modulo n** is an integer g such that its powers g¹, g², g³, ... generate all integers coprime to n (modulo n). Equivalently, g is a primitive root mod n if its multiplicative order equals φ(n). ## Why It Matters Primitive roots provide a "logarithm structure" for modular arithmetic, allowing multiplication mod n to be converted into addition of exponents—this underpins the discrete logarithm problem that secures cryptographic systems like Diffie-Hellman key exchange. They exist only for n = 1, 2, 4, p^k, or 2p^k (where p is odd prime), making them rare but powerful when available.