Primitive Roots - Applications

Primitive roots enable powerful applications in cryptography, pseudorandom number generation, and solving higher-degree congruences. The discrete logarithm problem, based on primitive roots, forms the security foundation for many cryptographic protocols.

TheoremDiscrete Logarithm Problem

Given a prime $p$ , a primitive root $g$ modulo $p$ , and an element $a \in (\mathbb{Z}/p\mathbb{Z})^*$ , the discrete logarithm problem (DLP) is to find the index $x$ such that: $g^x \equiv a \pmod{p}$

No polynomial-time algorithm is known for solving DLP in general, making it cryptographically useful.

The presumed hardness of DLP underpins Diffie-Hellman key exchange, ElGamal encryption, and the Digital Signature Algorithm (DSA).

ExampleDiscrete Logarithm

Find $x$ such that $2^x \equiv 7 \pmod{11}$ , where $2$ is a primitive root modulo $11$ .

From our index table: $\text{ind}_2(7) = 7$ , so $x = 7$ .

Verify: $2^7 = 128 = 11 \cdot 11 + 7 \equiv 7 \pmod{11}$ . ✓

For large primes (hundreds of digits), computing such logarithms is computationally infeasible with current algorithms.

TheoremDiffie-Hellman Key Exchange

Alice and Bob agree on a large prime $p$ and a primitive root $g$ modulo $p$ (public).

Alice chooses secret $a$ , sends $A = g^a \bmod p$ to Bob
Bob chooses secret $b$ , sends $B = g^b \bmod p$ to Alice
Alice computes $K = B^a = g^{ab} \bmod p$
Bob computes $K = A^b = g^{ab} \bmod p$

Both arrive at the same shared secret $K = g^{ab}$ . An eavesdropper seeing $g^a$ and $g^b$ must solve DLP to find $a$ or $b$ .

ExampleDiffie-Hellman Example

Use $p = 23, g = 5$ (primitive root modulo $23$ ).

Alice chooses $a = 6$ : $A = 5^6 = 15625 \equiv 8 \pmod{23}$ Bob chooses $b = 15$ : $B = 5^{15} \pmod{23}$

Computing $B$ : $5^{15} = 5^{11} \cdot 5^4 \equiv (-1) \cdot 4 = -4 \equiv 19 \pmod{23}$

Shared secret:

Alice: $K = 19^6 \pmod{23}$
Bob: $K = 8^{15} \pmod{23}$

Both compute to the same value $K = 5^{90} \pmod{23}$ .

TheoremArtin's Conjecture on Primitive Roots

Let $a > 1$ be an integer that is not a perfect power. Artin conjectured that there are infinitely many primes $p$ for which $a$ is a primitive root modulo $p$ .

Moreover, the density of such primes among all primes is conjectured to be a computable constant $A(a)$ (Artin's constant $\approx 0.3739$ when $a$ is not a perfect square).

While still technically open, Artin's conjecture has been proven conditionally on the generalized Riemann hypothesis.

ExampleSmall Primitive Roots

The integer $2$ is a primitive root for primes: $p \in \{3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, \ldots\}$

The integer $3$ is a primitive root for primes: $p \in \{2, 5, 7, 17, 19, 29, 31, 43, 53, 79, \ldots\}$

Artin predicts that about $37.39\%$ of primes have $2$ as a primitive root.

TheoremOrder and Polynomial Congruences

Using primitive roots, polynomial congruences $f(x) \equiv 0 \pmod{p}$ can be transformed. For instance, to solve $x^n \equiv a \pmod{p}$ :

Let $g$ be a primitive root. Write $x = g^y$ and $a = g^b$ where $b = \text{ind}_g(a)$ . Then: $g^{ny} \equiv g^b \pmod{p} \implies ny \equiv b \pmod{p-1}$

This linear congruence has $\gcd(n, p-1)$ solutions when $\gcd(n, p-1) \mid b$ .

ExampleSolving $x^3 \equiv 2 \pmod{7}$

With $g = 3$ (primitive root modulo $7$ ), write $x = 3^y$ and $2 = 3^2$ : $3^{3y} \equiv 3^2 \pmod{7} \implies 3y \equiv 2 \pmod{6}$

Since $\gcd(3, 6) = 3$ and $3 \nmid 2$ , there are no solutions.

Indeed, testing: $1^3 = 1, 2^3 = 8 \equiv 1, 3^3 = 27 \equiv 6, 4^3 = 64 \equiv 1, 5^3 = 125 \equiv 6, 6^3 = 216 \equiv 6 \pmod{7}$ .

No cube equals $2$ modulo $7$ .

Remark

Primitive roots provide both theoretical insights and practical algorithms. They bridge classical number theory with modern cryptography, demonstrating how ancient mathematical concepts find new life in digital security.

These applications show how primitive roots transform abstract group theory into concrete computational tools with real-world impact.