Hubbry Logo
search
logo
Primitive root modulo n avatar
Primitive root modulo n
Primitive root modulo n
current hub
P

Primitive root modulo n

logo
Community Hub0 Subscribers
Read side by side
Primitive root modulo n
View on Wikipedia
from Wikipedia

In modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gk ≡ a (mod n). Such a value k is called the index or discrete logarithm of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.

Gauss defined primitive roots in Article 57 of the Disquisitiones Arithmeticae (1801), where he credited Euler with coining the term. In Article 56 he stated that Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime n. In fact, the Disquisitiones contains two proofs: The one in Article 54 is a nonconstructive existence proof, while the proof in Article 55 is constructive.

A primitive root exists if and only if n is 1, 2, 4, pk or 2pk, where p is an odd prime and k > 0. For all other values of n the multiplicative group of integers modulo n is not cyclic.[1][2][3] This was first proved by Gauss.[4]

Elementary example

[edit]

The number 3 is a primitive root modulo 7[5] because

Here we see that the period of 3k modulo 7 is 6. The remainders in the period, which are 3, 2, 6, 4, 5, 1, form a rearrangement of all nonzero remainders modulo 7, implying that 3 is indeed a primitive root modulo 7. This derives from the fact that a sequence (gk modulo n) always repeats after some value of k, since modulo n produces a finite number of values. If g is a primitive root modulo n and n is prime, then the period of repetition is n − 1. Permutations created in this way (and their circular shifts) have been shown to be Costas arrays.

Definition

[edit]

If n is a positive integer, the integers from 1 to n − 1 that are coprime to n (or equivalently, the congruence classes coprime to n) form a group, with multiplication modulo n as the operation; it is denoted by ×
n, and is called the group of units modulo n, or the group of primitive classes modulo n. As explained in the article multiplicative group of integers modulo n, this multiplicative group (×
n) is cyclic if and only if n is equal to 2, 4, pk, or 2pk where pk is a power of an odd prime number.[6][2][7] When (and only when) this group ×
n is cyclic, a generator of this cyclic group is called a primitive root modulo n[8] (or in fuller language primitive root of unity modulo n, emphasizing its role as a fundamental solution of the roots of unity polynomial equations Xm
 − 1 in the ring n), or simply a primitive element of ×
n.

When ×
n is non-cyclic, such primitive elements mod n do not exist. Instead, each prime component of n has its own sub-primitive roots (see 15 in the examples below).

For any n (whether or not ×
n is cyclic), the order of ×
n is given by Euler's totient function φ(n) (sequence A000010 in the OEIS). And then, Euler's theorem says that aφ(n) ≡ 1 (mod n) for every a coprime to n; the lowest power of a that is congruent to 1 modulo n is called the multiplicative order of a modulo n. In particular, for a to be a primitive root modulo n, aφ(n) has to be the smallest power of a that is congruent to 1 modulo n.

Examples

[edit]

For example, if n = 14 then the elements of ×
n are the congruence classes {1, 3, 5, 9, 11, 13}; there are φ(14) = 6 of them. Here is a table of their powers modulo 14: 

 x     x, x2, x3, ... (mod 14)
 1 :   1
 3 :   3,  9, 13, 11,  5,  1 
 5 :   5, 11, 13,  9,  3,  1
 9 :   9, 11,  1
11 :  11,  9,  1
13 :  13,  1

The order of 1 is 1, the orders of 3 and 5 are 6, the orders of 9 and 11 are 3, and the order of 13 is 2. Thus, 3 and 5 are the primitive roots modulo 14.

For a second example let n = 15 . The elements of ×
15 are the congruence classes {1, 2, 4, 7, 8, 11, 13, 14}; there are φ(15) = 8 of them. 

 x     x, x2, x3, ... (mod 15)
 1 :   1
 2 :   2,  4,  8, 1 
 4 :   4,  1
 7 :   7,  4, 13, 1
 8 :   8,  4,  2, 1
11 :  11,  1
13 :  13,  4,  7, 1
14 :  14,  1

Since there is no number whose order is 8, there are no primitive roots modulo 15. Indeed, λ(15) = 4, where λ is the Carmichael function. (sequence A002322 in the OEIS)

Table of primitive roots

[edit]

Numbers that have a primitive root are of the shape

= {1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ...}.[9]

These are the numbers with kept also in the sequence A033948 in the OEIS.

The following table lists the primitive roots modulo n up to :

⁠⁠ primitive roots modulo ⁠⁠ order
((sequence A000010 in the OEIS)) 		exponent
((sequence A002322 in the OEIS))
1 0 1 1
2 1 1 1
3 2 2 2
4 3 2 2
5 2, 3 4 4
6 5 2 2
7 3, 5 6 6
8 4 2
9 2, 5 6 6
10 3, 7 4 4
11 2, 6, 7, 8 10 10
12 4 2
13 2, 6, 7, 11 12 12
14 3, 5 6 6
15 8 4
16 8 4
17 3, 5, 6, 7, 10, 11, 12, 14 16 16
18 5, 11 6 6
19 2, 3, 10, 13, 14, 15 18 18
20 8 4
21 12 6
22 7, 13, 17, 19 10 10
23 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 22 22
24 8 2
25 2, 3, 8, 12, 13, 17, 22, 23 20 20
26 7, 11, 15, 19 12 12
27 2, 5, 11, 14, 20, 23 18 18
28 12 6
29 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27 28 28
30 8 4
31 3, 11, 12, 13, 17, 21, 22, 24 30 30

Properties

[edit]

Gauss proved[10] that for any prime number p (with the sole exception of p = 3), the product of its primitive roots is congruent to 1 modulo p.

He also proved[11] that for any prime number p, the sum of its primitive roots is congruent to μ(p − 1) modulo p, where μ is the Möbius function.

For example,

p = 3, μ(2) = −1. The primitive root is 2.
p = 5, μ(4) = 0. The primitive roots are 2 and 3.
p = 7, μ(6) = 1. The primitive roots are 3 and 5.
p = 31, μ(30) = −1. The primitive roots are 3, 11, 12, 13, 17, 21, 22 and 24.

E.g., the product of the latter primitive roots is , and their sum is .

If is a primitive root modulo the prime , then .

Artin's conjecture on primitive roots states that a given integer a that is neither a perfect square nor −1 is a primitive root modulo infinitely many primes.

Finding primitive roots

[edit]

No simple general formula to compute primitive roots modulo n is known.[a][b] There are however methods to locate a primitive root that are faster than simply trying out all candidates. If the multiplicative order (its exponent) of a number m modulo n is equal to (the order of ×
n), then it is a primitive root. In fact the converse is true: If m is a primitive root modulo n, then the multiplicative order of m is We can use this to test a candidate m to see if it is primitive.

For first, compute Then determine the different prime factors of , say p1, ..., pk. Finally, compute

using a fast algorithm for modular exponentiation such as exponentiation by squaring. A number g for which these k results are all different from 1 is a primitive root.

The number of primitive roots modulo n, if there are any, is equal to[12]

since, in general, a cyclic group with r elements has generators.

For prime n, this equals , and since the generators are very common among {2, ..., n−1} and thus it is relatively easy to find one.[13]

If g is a primitive root modulo p, then g is also a primitive root modulo all powers pk unless gp−1 ≡ 1 (mod p2); in that case, g + p is.[14]

If g is a primitive root modulo pk, then g is also a primitive root modulo all smaller powers of p.

If g is a primitive root modulo pk, then either g or g + pk (whichever one is odd) is a primitive root modulo 2pk.[14]

Finding primitive roots modulo p is also equivalent to finding the roots of the (p − 1)st cyclotomic polynomial modulo p.

Order of magnitude of primitive roots

[edit]

The least primitive root gp modulo p (in the range 1, 2, ..., p − 1) is generally small.

Upper bounds

[edit]

Burgess (1962) proved[15][16] that for every ε > 0 there is a C such that

Grosswald (1981) proved[15][17] that if , then

Shoup (1990, 1992) proved,[18] assuming the generalized Riemann hypothesis, that gp = O(log6 p).

Lower bounds

[edit]

Fridlander (1949) and Salié (1950) proved[15] that there is a positive constant C such that for infinitely many primes gp > C log p.

It can be proved[15] in an elementary manner that for any positive integer M there are infinitely many primes such that M < gp < p − M.

Applications

[edit]

A primitive root modulo n is often used in pseudorandom number generators[19] and cryptography, including the Diffie–Hellman key exchange scheme. Sound diffusers have been based on number-theoretic concepts such as primitive roots and quadratic residues.[20][21]

See also

[edit]

Footnotes

[edit]

References

[edit]

Sources

[edit]
  • Carella, N. A. (2015). "Least Prime Primitive Roots". International Journal of Mathematics and Computer Science. 10 (2): 185–194. arXiv:1709.01172.

The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Primitive root modulo n

View on Grokipedia
from Grokipedia
In number theory, a primitive root modulo n is an integer g coprime to the positive integer n such that the multiplicative order of g modulo n—the smallest positive integer k for which gk ≡ 1 (mod n)—equals Euler's totient function φ(n), which counts the number of integers up to n that are coprime to n.[1][2] Equivalently, the powers of g modulo n generate every element of the multiplicative group of integers modulo n, denoted (Z/nZ)×, making g a generator of this group when it is cyclic.[3][4] Primitive roots modulo n do not exist for every n; they exist if and only if n = 2, n = 4, n = pr, or n = 2pr, where p is an odd prime and r is a positive integer.[2] For prime p, the number of primitive roots modulo p is exactly φ(p - 1).[5] When they exist, primitive roots characterize the cyclicity of (Z/nZ)×, a property that holds precisely under the above conditions on n.[6] Primitive roots play a central role in analytic and algebraic number theory, enabling the definition of discrete logarithms modulo n—the problem of finding k such that a ≡ gk (mod n) for a in (Z/nZ)×—which underpins algorithms for solving congruences and studying the structure of finite abelian groups.[4] They also facilitate computations like indices (discrete logs base g) and appear in applications such as analyzing repeating decimal expansions and modeling random processes like card shuffling via riffle shuffles.[7][8]

Fundamentals

Definition

In number theory, Euler's totient function ϕ(n)\phi(n) counts the number of positive integers up to nn that are relatively prime to nn, and is given by the formula ϕ(n)=n∏p∣n(1−1p)\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right), where the product is over the distinct prime factors pp of nn.[9][10] An integer gg is a primitive root modulo nn if gcd⁡(g,n)=1\gcd(g, n) = 1 and the multiplicative order of gg modulo nn is exactly ϕ(n)\phi(n).[9][11] The multiplicative order of gg modulo nn is defined as the smallest positive integer kk such that gk≡1(modn)g^k \equiv 1 \pmod{n}.[9][12] In the context of group theory, a primitive root gg modulo nn generates the multiplicative group of integers modulo nn, denoted (Z/nZ)∗(\mathbb{Z}/n\mathbb{Z})^*, which consists of the residue classes coprime to nn under multiplication modulo nn.[6] This group has order ϕ(n)\phi(n), and the powers g0,g1,…,gϕ(n)−1g^0, g^1, \dots, g^{\phi(n)-1} modulo nn are all distinct and comprise every element of (Z/nZ)∗(\mathbb{Z}/n\mathbb{Z})^*, thereby making the group cyclic.[9][6]

Elementary Example

A simple illustration of a primitive root occurs modulo 5, a prime number for which Euler's totient function φ(5) equals 4, meaning the multiplicative group of integers modulo 5 consists of the four units {1, 2, 3, 4} that are coprime to 5.[10][13] Consider g = 2. The successive powers of 2 modulo 5 are computed as follows:
k2^k mod 5
01
12
24
33
These powers generate all four units exactly once before repeating, confirming that the multiplicative order of 2 modulo 5 is 4, equal to φ(5), so 2 is a primitive root modulo 5.[13] In contrast, consider g = 4. The powers of 4 modulo 5 are:
k4^k mod 5
01
14
21
Here, the powers cycle every 2 steps, giving 4 a multiplicative order of 2, which is less than φ(5) = 4, so 4 is not a primitive root modulo 5.[12]

Existence Conditions

For Prime Moduli

When $ n = p $ is a prime number, primitive roots always exist modulo $ p $. This follows from the fact that the multiplicative group $ (\mathbb{Z}/p\mathbb{Z})^\times $ is cyclic of order $ p-1 $, as established by Fermat's Little Theorem, which states that every non-zero element modulo $ p $ satisfies $ a^{p-1} \equiv 1 \pmod{p} $, implying the group order is $ \phi(p) = p-1 $.[5] A primitive root modulo $ p $ is then a generator of this cyclic group. The cyclicity of $ (\mathbb{Z}/p\mathbb{Z})^\times $ for prime $ p $ was rigorously proved by Carl Friedrich Gauss in 1801, utilizing properties of quadratic residues to demonstrate the existence of generators.[14] Gauss's proof in Disquisitiones Arithmeticae shows that the group structure ensures elements of order exactly $ p-1 $, confirming the presence of primitive roots. A standard proof of existence uses the factorization $ x^{p-1} - 1 = \prod_{d \mid p-1} \Phi_d(x) $ over $ \mathbb{F}p $, where $ \Phi_d(x) $ is the d-th cyclotomic polynomial of degree $ \phi(d) $. Since $ x^{p-1} - 1 $ has exactly $ p-1 $ distinct roots (all nonzero elements by Fermat's Little Theorem) and the total degree is $ \sum{d \mid p-1} \phi(d) = p-1 $, each $ \Phi_d(x) $ must have exactly $ \phi(d) $ roots in $ \mathbb{F}p $. In particular, $ \Phi{p-1}(x) $ has $ \phi(p-1) $ roots, which are elements of order exactly $ p-1 $, i.e., primitive roots. Thus, the number of primitive roots modulo $ p $ is exactly $ \phi(p-1) > 0 $.[15][5]

For Composite Moduli

Primitive roots exist modulo a composite integer nn if and only if n=2n = 2, n=4n = 4, n=pkn = p^k, or n=2pkn = 2p^k, where pp is an odd prime and k≥1k \geq 1.[16] For other composite forms, such as higher powers of 2 or products involving multiple distinct odd primes, the multiplicative group (Z/nZ)∗(\mathbb{Z}/n\mathbb{Z})^* is not cyclic, so no element achieves order ϕ(n)\phi(n).[16] Non-existence arises in cases like powers of 2 greater than 4; for n=8n = 8, ϕ(8)=4\phi(8) = 4, but every odd residue modulo 8 satisfies a2≡1(mod8)a^2 \equiv 1 \pmod{8}, so the maximum order is 2.[17] Similarly, for products of distinct odd primes like n=15=3×5n = 15 = 3 \times 5, ϕ(15)=8\phi(15) = 8, but the maximum order is lcm⁡(ϕ(3),ϕ(5))=lcm⁡(2,4)=4<8\operatorname{lcm}(\phi(3), \phi(5)) = \operatorname{lcm}(2, 4) = 4 < 8.[16] The Chinese Remainder Theorem plays a key role, as (Z/nZ)∗≅∏(Z/pikiZ)∗(\mathbb{Z}/n\mathbb{Z})^* \cong \prod (\mathbb{Z}/p_i^{k_i}\mathbb{Z})^* when n=∏pikin = \prod p_i^{k_i}, and the order of an element modulo nn is the least common multiple of its orders modulo each prime power factor.[18] Thus, (Z/nZ)∗(\mathbb{Z}/n\mathbb{Z})^* is cyclic if and only if each component group is cyclic, which fails for 2k2^k with k≥3k \geq 3 or when multiple odd prime powers are present, as their exponent structures do not align to yield a single generator of full order ϕ(n)\phi(n).[16] Explicit constructions of primitive roots for allowable composite moduli often involve lifting from lower powers via Hensel's lemma or direct adjustments. For prime powers pkp^k with odd prime pp, if gg is a primitive root modulo pkp^k, then g+tpkg + t p^k for suitable tt (0 to p−1p-1) yields the primitive roots modulo pk+1p^{k+1} that are congruent to gg modulo pkp^k; specifically, there are p−1p-1 such tt when k=1k=1 and pp such tt when k≥2k \geq 2.[19] For forms like 2pk2p^k, a primitive root modulo pkp^k can be adjusted (e.g., adding pkp^k if necessary to make it odd) to serve modulo 2pk2p^k, combining via the Chinese Remainder Theorem.[16]

Examples and Data

Specific Examples

A classic example of a primitive root occurs modulo 7, where ϕ(7)=6\phi(7)=6 and the integer 3 generates the multiplicative group. To verify, compute the powers of 3 modulo 7: 31≡33^1 \equiv 3, 32≡23^2 \equiv 2, 33≡63^3 \equiv 6, 34≡43^4 \equiv 4, 35≡53^5 \equiv 5, and 36≡13^6 \equiv 1. Since the order is 6, matching ϕ(7)\phi(7), 3 is primitive. Alternatively, confirm the order by checking that 36/q≢1(mod7)3^{6/q} \not\equiv 1 \pmod{7} for each prime qq dividing 6 (i.e., q=2,3q=2,3): 33≡6≢13^3 \equiv 6 \not\equiv 1 and 32≡2≢13^2 \equiv 2 \not\equiv 1.[20][8] Modulo 9, where ϕ(9)=6\phi(9)=6, the integer 2 serves as a primitive root. The powers are 21≡22^1 \equiv 2, 22≡42^2 \equiv 4, 23≡82^3 \equiv 8, 24≡72^4 \equiv 7, 25≡52^5 \equiv 5, and 26≡1(mod9)2^6 \equiv 1 \pmod{9}, yielding order 6. Checking against divisors: 23≡8≢12^3 \equiv 8 \not\equiv 1 and 22≡4≢1(mod9)2^2 \equiv 4 \not\equiv 1 \pmod{9}.[21] For modulo 14, with ϕ(14)=6\phi(14)=6, 3 is again a primitive root. Compute: 31≡33^1 \equiv 3, 32≡93^2 \equiv 9, 33≡133^3 \equiv 13, 34≡113^4 \equiv 11, 35≡53^5 \equiv 5, 36≡1(mod14)3^6 \equiv 1 \pmod{14}. The order is 6, as 33≡13≢13^3 \equiv 13 \not\equiv 1 and 32≡9≢1(mod14)3^2 \equiv 9 \not\equiv 1 \pmod{14}.[22] Primitive roots do not exist for all nn; consider modulo 8, where ϕ(8)=4\phi(8)=4 but the unit group {1,3,5,7}\{1,3,5,7\} has maximum order 2. For instance, 32≡13^2 \equiv 1, 52≡15^2 \equiv 1, and 72≡1(mod8)7^2 \equiv 1 \pmod{8}, so no element achieves order 4.[23] Similarly, modulo 15 with ϕ(15)=8\phi(15)=8, the maximum order is 4, as the group is isomorphic to C4×C2C_4 \times C_2. Elements like 2 yield 24≡1(mod15)2^4 \equiv 1 \pmod{15}, and 7 gives 74≡1(mod15)7^4 \equiv 1 \pmod{15}, but no order reaches 8.[24]

Table of Primitive Roots

The smallest primitive root modulo a prime pp is the least positive integer gg such that the multiplicative order of gg modulo pp is ϕ(p)=p−1\phi(p) = p-1, where ϕ\phi denotes Euler's totient function.[25] For each such pp, there are exactly ϕ(p−1)\phi(p-1) primitive roots modulo pp.[11] The following table lists the primes p≤200p \leq 200, their ϕ(p)\phi(p), and the smallest primitive root gg for each, based on verified computational data.[25]
ppϕ(p)\phi(p)Smallest gg
211
322
542
763
11102
13122
17163
19182
23225
29282
31303
37362
41406
43423
47465
53522
59582
61602
67662
71707
73725
79783
83822
89883
97965
1011002
1031025
1071062
1091086
1131123
1271263
1311302
1371363
1391382
1491482
1511506
1571565
1631622
1671665
1731722
1791782
1811802
19119019
1931925
1971962
1991983
Primitive roots also exist modulo certain composite numbers, specifically powers of odd primes pkp^k (k≥1k \geq 1) and twice such powers (2pk2p^k). The following table provides examples for small prime powers, including their ϕ(n)\phi(n) and smallest primitive root gg.[11]
nnϕ(n)\phi(n)Smallest gg
423
962
25202
27182
49423
Among the smallest primitive roots for primes, small values such as 2, 3, and 5 appear frequently; for instance, 2 serves as the smallest primitive root for 22 of the 46 primes up to 199.[25] Artin's conjecture posits that 2 is a primitive root modulo infinitely many primes, a statement that holds under the generalized Riemann hypothesis.[26]

Properties

Basic Properties

A primitive root modulo nn, denoted gg, generates the multiplicative group of integers modulo nn, denoted (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^\times. Specifically, the set {gkmod  n∣k=0,1,…,ϕ(n)−1}\{g^k \mod n \mid k = 0, 1, \dots, \phi(n)-1\} equals (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^\times, where ϕ\phi is Euler's totient function, meaning every element coprime to nn can be expressed uniquely as a power of gg modulo nn.[27][4] Among the powers of a primitive root gg, the element gkmod  ng^k \mod n is itself a primitive root if and only if gcd⁡(k,ϕ(n))=1\gcd(k, \phi(n)) = 1. This follows from the order of gkg^k being ϕ(n)/gcd⁡(k,ϕ(n))\phi(n)/\gcd(k, \phi(n)), which equals ϕ(n)\phi(n) precisely when kk is coprime to ϕ(n)\phi(n). In particular, the modular inverse g−1mod  ng^{-1} \mod n is a primitive root, as it equals gϕ(n)−1mod  ng^{\phi(n)-1} \mod n and gcd⁡(ϕ(n)−1,ϕ(n))=1\gcd(\phi(n)-1, \phi(n)) = 1.[27][4] When primitive roots exist modulo nn, their total number is exactly ϕ(ϕ(n))\phi(\phi(n)). This count arises because the primitive roots are precisely the generators of (Z/nZ)×(\mathbb{Z}/n\mathbb{Z})^\times, and the number of such generators in a cyclic group of order ϕ(n)\phi(n) is given by Euler's totient function applied to the group order.[27][4] The concept of a primitive root enables the definition of the index (or discrete logarithm) base gg modulo nn. For any a∈(Z/nZ)×a \in (\mathbb{Z}/n\mathbb{Z})^\times, the index ind⁡g(a)\operatorname{ind}_g(a) is the unique integer kk with 0≤k<ϕ(n)0 \leq k < \phi(n) such that a≡gk(modn)a \equiv g^k \pmod{n}. This provides a logarithmic encoding of the group elements, satisfying properties like ind⁡g(ab)≡ind⁡g(a)+ind⁡g(b)(modϕ(n))\operatorname{ind}_g(ab) \equiv \operatorname{ind}_g(a) + \operatorname{ind}_g(b) \pmod{\phi(n)}.[27][4]

Advanced Properties

One advanced property concerns the extension of primitive roots from a prime modulus to higher powers of that prime. For an odd prime pp and a primitive root gg modulo pp, Hensel's lemma can be applied to lift gg to a primitive root modulo pkp^k for any k≥2k \geq 2. Specifically, there exists an integer tt with 0≤t<p0 \leq t < p such that g+tpg + t p is a primitive root modulo p2p^2, and this construction extends inductively to higher powers, ensuring the order remains ϕ(pk)=pk−1(p−1)\phi(p^k) = p^{k-1}(p-1).[28] Primitive roots modulo a prime pp are intimately connected to cyclotomic polynomials. Since the multiplicative group (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times is cyclic of order p−1p-1, the primitive roots are exactly the elements of order p−1p-1, which correspond to the roots of the (p−1)(p-1)-th cyclotomic polynomial Φp−1(x)\Phi_{p-1}(x) over the finite field Fp\mathbb{F}_p. This polynomial, irreducible over the rationals, splits completely into ϕ(p−1)\phi(p-1) linear factors in Fp\mathbb{F}_p, with each root generating the group.[29] For specific small integers like 2 or 5, determining when they serve as primitive roots modulo an odd prime pp relies on checking their order against the prime factors of p−1p-1. In particular, 2 is a primitive root modulo pp if and only if 2(p−1)/q≢1(modp)2^{(p-1)/q} \not\equiv 1 \pmod{p} for every prime qq dividing p−1p-1, which includes conditions such as 2 being a quadratic non-residue modulo pp (for q=2q=2) and similar higher-order checks for other qq. Analogous criteria apply to 5, requiring 5(p−1)/q≢1(modp)5^{(p-1)/q} \not\equiv 1 \pmod{p} for all such qq. Under the generalized Riemann hypothesis (GRH), the proportion of primes pp for which 2 is a primitive root is given by Artin's constant C=∏q≥2(1−1q(q−1))≈0.3739558136C = \prod_{q \geq 2} \left(1 - \frac{1}{q(q-1)}\right) \approx 0.3739558136, confirming a positive density for such primes.[30]

Computation Methods

Testing Procedures

To determine whether a given integer gg (with gcd⁡(g,n)=1\gcd(g, n) = 1) is a primitive root modulo nn, where primitive roots exist, the multiplicative order of gg modulo nn must equal ϕ(n)\phi(n), with ϕ\phi denoting Euler's totient function. The multiplicative order is the smallest positive integer kk such that gk≡1(modn)g^k \equiv 1 \pmod{n}.[31] A prerequisite for testing is the complete factorization of ϕ(n)\phi(n) into its prime factors.[32] The standard deterministic procedure verifies that the order is exactly ϕ(n)\phi(n) by checking that gϕ(n)/q≢1(modn)g^{\phi(n)/q} \not\equiv 1 \pmod{n} for every distinct prime divisor qq of ϕ(n)\phi(n). If this condition holds for all such qq, then gg is a primitive root modulo nn.[31][32] For example, test g=2g = 2 modulo n=11n = 11. Here, ϕ(11)=10=2×5\phi(11) = 10 = 2 \times 5, so the prime divisors are q=2q = 2 and q=5q = 5. Compute 210/2=25=32≡−1≢1(mod11)2^{10/2} = 2^5 = 32 \equiv -1 \not\equiv 1 \pmod{11} and 210/5=22=4≢1(mod11)2^{10/5} = 2^2 = 4 \not\equiv 1 \pmod{11}. Since both checks pass, 22 is a primitive root modulo 1111.[31] The time complexity of this test is O(ω(ϕ(n))⋅log⁡n)O(\omega(\phi(n)) \cdot \log n), where ω(ϕ(n))\omega(\phi(n)) is the number of distinct prime factors of ϕ(n)\phi(n), as it involves ω(ϕ(n))\omega(\phi(n)) modular exponentiations, each performed in O(log⁡n)O(\log n) time using efficient methods like binary exponentiation.[32]

Efficient Algorithms

One efficient approach to finding a primitive root modulo a prime pp is the probabilistic random selection method. Select a random integer gg with 1<g<p1 < g < p and gcd⁡(g,p)=1\gcd(g, p) = 1, then test whether gg is a primitive root using the standard order verification procedure (which assumes the factorization of p−1p-1). The probability of success is ϕ(p−1)/(p−1)\phi(p-1)/(p-1), which is asymptotically equal to Artin's constant A≈0.3739558136A \approx 0.3739558136 under the generalized Riemann hypothesis (GRH).[30] Unconditionally, this proportion is positive for sufficiently large pp, ensuring that the expected number of trials is bounded by a constant. Each test requires computing a small number of modular exponentiations, leading to an overall expected time complexity of O(log⁡2p)O(\log^2 p) per trial assuming fast exponentiation, or O(log⁡4p)O(\log^4 p) in more conservative models without precomputed factorizations.[33] For deterministic methods, a sequential search starting from small candidates g=2,3,5,…g = 2, 3, 5, \dots is optimized under GRH. The smallest primitive root g(p)g(p) satisfies g(p)=O(log⁡6p)g(p) = O(\log^6 p), allowing the algorithm to test only up to this bound before guaranteeing success.[34] With the factorization of p−1p-1 available, the total time is polynomial in log⁡p\log p, specifically O((log⁡p)7⋅ω(p−1)⋅log⁡2p)O((\log p)^7 \cdot \omega(p-1) \cdot \log^2 p), where ω(p−1)\omega(p-1) is the number of distinct prime factors of p−1p-1 (typically O(log⁡p/log⁡log⁡p)O(\log p / \log \log p). This yields a deterministic polynomial-time algorithm under GRH, improving on unconditional searches that may require testing up to p1/4+o(1)p^{1/4 + o(1)} candidates.[33] Recent advancements include pseudo-deterministic algorithms that find a primitive root with high probability using a fixed seed, matching the O(log⁡2p)O(\log^2 p) expected time of Las Vegas methods without randomness. These construct a primitive root by combining quadratic non-residues for each prime factor of p−1p-1, using sequential testing for large factors and deterministic selection for small ones; the approach is unconditional but leverages GRH bounds for efficiency in verification.[34] For composite moduli nn where primitive roots exist (e.g., n=2,4,pk,n = 2, 4, p^k, or 2pk2p^k for odd prime pp), similar strategies apply by adapting the search to the structure of ϕ(n)\phi(n) and testing against its prime factors, though the success probability decreases with the number of prime power factors.[33]

Asymptotic Bounds

Upper Bounds on Smallest Primitive Root

The study of upper bounds on the smallest primitive root g(p)g(p) modulo a prime pp has evolved through key theoretical advances in analytic number theory, focusing on character sum estimates to guarantee the existence of small generators of the multiplicative group modulo pp. Early results relied on the Pólya–Vinogradov inequality for non-trivial Dirichlet characters, yielding g(p)≪p1/2(log⁡p)2g(p) \ll p^{1/2} (\log p)^2, but Vinogradov improved this in 1952 to g(p)<pc/log⁡log⁡pg(p) < p^{c / \log \log p} for some absolute constant c>0c > 0, marking the first subpolynomial unconditional bound. This exponent approaching 0 as p→∞p \to \infty highlighted the potential for even smaller primitive roots, though the constant cc remained unspecified. A major breakthrough came with Burgess's 1962 theorem, which uses higher-degree character sum estimates to establish g(p)≪p1/4+ϵg(p) \ll p^{1/4 + \epsilon} for any ϵ>0\epsilon > 0. The method's optimal exponent was later refined to 1/(4e)+ϵ≈0.1518+ϵ1/(4\sqrt{e}) + \epsilon \approx 0.1518 + \epsilon, applicable to all odd primes pp, by leveraging the full strength of Burgess's inequality on sums over intervals. Unconditionally, these results imply g(p)≤po(1)g(p) \leq p^{o(1)} as p→∞p \to \infty. Recent explicit versions, such as those by McGown and Trudgian in 2019, provide concrete constants tightening the Burgess bound for practical ranges of pp, with further refinements in 2023 by Kerr and others optimizing the character sum constants for denser sets of primes.[35] Under the Generalized Riemann Hypothesis (GRH), Ankeny proved in 1952 that g(p)=O(log⁡2p)g(p) = O(\log^2 p), a polylogarithmic bound derived from zero-free regions of Dirichlet L-functions associated to characters modulo p−1p-1. This conditional result aligns with heuristic expectations that g(p)g(p) is typically around log⁡p\log p, and it has influenced algorithmic approaches despite remaining unproven unconditionally.

Lower Bounds on Smallest Primitive Root

The smallest primitive root $ g(n) $ satisfies the trivial lower bound $ g(n) \ge 2 $ for $ n > 2 $, since 1 has multiplicative order 1 and cannot generate the full group $ (\mathbb{Z}/n\mathbb{Z})^\times $. For prime moduli $ p $, this bound is sharp in the sense that $ g(p) = 2 $ for some primes (e.g., $ p = 5, 11, 29 $), but more substantial lower bounds hold for infinitely many primes, showing that $ g(p) $ can be forced to be relatively large. In 1944, S. S. Pillai established that there exists a positive constant $ c $ such that $ g(p) > c \log \log p $ for infinitely many primes $ p $. This was improved by V. Fridlender (1949) and H. Salié (1957) to $ g(p) > c \log p $ for infinitely many $ p $, using Linnik's theorem on primes in arithmetic progressions. Further progress was made by M. B. Gupta and V. K. Ram Murty in 1984, who showed that $ g(p) > c (\log p \log \log p) / \log \log \log p $ for some $ c > 0 $ and infinitely many primes $ p $. These omega results demonstrate that $ \limsup_{p \to \infty} g(p) / ((\log p \log \log p) / \log \log \log p) > 0 $, highlighting that the smallest primitive root can be asymptotically as large as the conjectured upper bound up to lower-order terms.[36] Artin's conjecture, proposed in 1927, asserts that for any integer $ a > 1 $ that is not -1 or a perfect square, the density of primes $ p $ for which $ a $ is a primitive root modulo $ p $ is the positive constant $ A = \prod_q (1 - 1/(q(q-1))) \approx 0.3739558 $, known as Artin's constant. This implies that $ g(p) = O(\log p \log \log p) $ for all primes $ p $, with the constant $ e^\gamma $ in the leading term under the conjecture, where $ \gamma $ is the Euler-Mascheroni constant. However, the conjecture remains unresolved as of 2025. Under the generalized Riemann hypothesis (GRH), C. Hooley proved in 1967 that the conjecture holds with the exact density $ A $. Unconditionally, D. R. Heath-Brown showed in 1986 that at most two prime numbers fail to be primitive roots modulo a positive proportion of primes, implying that for all but at most two exceptions among small primes, the Artin density holds. Additionally, under GRH, H. L. Montgomery showed that $ g(p) > c \log p \log \log p $ for infinitely many $ p $, nearly matching the conjectured upper bound. Unconditionally, it is known that $ g(p) > (\log p)^{1-\varepsilon} $ for any $ \varepsilon > 0 $ and all but $ o(\pi(x)) $ primes $ p \le x $, reflecting that the smallest primitive root tends to grow with $ p $ for the majority of primes, though exceptions where $ g(p) $ is small occur with positive density under Artin's conjecture.

Applications

In Number Theory

Primitive roots modulo nn are fundamental in the discrete logarithm problem within number theory. For a prime pp admitting a primitive root gg, the discrete logarithm indg(a)\mathrm{ind}_g(a) of an integer aa not divisible by pp is the unique exponent kk with 0≤k<p−10 \leq k < p-1 satisfying gk≡a(modp)g^k \equiv a \pmod{p}. This representation transforms multiplicative relations into additive ones modulo ϕ(p)=p−1\phi(p) = p-1, aiding the analysis of congruences and cyclic group structures. The baby-step giant-step algorithm, introduced by Daniel Shanks, computes indg(a)\mathrm{ind}_g(a) in O(plog⁡p)O(\sqrt{p} \log p) time and O(p)O(\sqrt{p}) space by dividing the search into small "baby steps" of powers gjg^j for j<p−1j < \sqrt{p-1} and "giant steps" of a⋅(g−mp−1)a \cdot (g^{-m \sqrt{p-1}}) for steps mm, matching via a hash table to resolve the exponent. For prime moduli, index calculus algorithms further accelerate discrete logarithm computation by factoring smooth elements in the field Fp\mathbb{F}_p, using a primitive root to express bases in logarithmic form and solving a linear system over the exponents modulo p−1p-1. These methods achieve subexponential time complexity Lp[1/2,c]L_p[1/2, c] for some constant c>0c > 0, leveraging the cyclicity ensured by the primitive root.[37] In the study of character sums, primitive roots facilitate the evaluation and properties of Gauss sums, which are central to analytic number theory. For a multiplicative character χ\chi modulo a prime pp, the Gauss sum is G(χ)=∑k=1p−1χ(k)e2πik/pG(\chi) = \sum_{k=1}^{p-1} \chi(k) e^{2\pi i k / p}. When χ\chi is primitive (not induced from a proper subfield) and the sum is reindexed using a primitive root gg via k=gj(modp)k = g^j \pmod{p}, it becomes G(χ)=∑j=0p−2χ(gj)ζjG(\chi) = \sum_{j=0}^{p-2} \chi(g^j) \zeta^j where ζ=e2πi/p\zeta = e^{2\pi i / p}; for non-principal primitive χ\chi, ∣G(χ)∣=p|G(\chi)| = \sqrt{p}, with the exact value involving the Jacobi symbol or roots of unity. This structure enables Stickelberger's theorem, which determines G(χ)G(\chi) explicitly in cyclotomic fields, and underpins proofs of quadratic reciprocity and estimates for incomplete sums like ∑χ(n)e2πiαn\sum \chi(n) e^{2\pi i \alpha n}. Primitive roots ensure the uniform distribution of indices, crucial for bounding error terms in these evaluations. Primitive roots also contribute indirectly to primality testing algorithms in number theory. Since every odd prime pp has a cyclic multiplicative group (Z/pZ)×(\mathbb{Z}/p\mathbb{Z})^\times of order p−1p-1, it admits primitive roots, whereas composite moduli often do not. Lucas's 1876 tests verify primality by checking the order of a base aa modulo nn: if aa has order dividing n−1n-1 but not any proper divisor, and similar conditions hold for factors of n−1n-1, it certifies nn prime by implying the existence of a generator of order n−1n-1. These criteria exploit the absence of primitive roots for certain composites (e.g., twice odd primes) to rule out non-primes efficiently, without explicitly finding a primitive root, though the tests align with the cyclic structure confirmed by one. Modern variants, like the Lucas-Lehmer test for Mersenne primes, generalize this order-checking approach.[38] Artin's primitive root conjecture provides a profound link between primitive roots and analytic number theory, particularly class number problems. The conjecture asserts that for any integer a≠−1a \neq -1 that is not a perfect square, there are infinitely many primes pp such that aa is a primitive root modulo pp, with a natural density of ∏q′(1−1/(q(q−1)))\prod_{q \prime} (1 - 1/(q(q-1))) under suitable conditions. Proving a positive density requires the generalized Riemann hypothesis for Artin LL-functions L(s,χ,K)L(s, \chi, K), where χ\chi are characters induced by the Galois representation attached to the extension generated by roots of xp−a=0x^p - a = 0; non-vanishing at s=1s=1 implies the infinitude via density arguments. This connects to class numbers of number fields, as the residue of L(s,χ,K)L(s, \chi, K) at s=1s=1 relates to the class number formula hK=wK∣ΔK∣Ress=1L(s,K)/(2π)[K:Q]/2h_K = w_K \sqrt{|\Delta_K|} \mathrm{Res}_{s=1} L(s, K) / (2\pi)^{[K:\mathbb{Q}]/2}, influencing bounds on primitive root distribution and analytic continuations in algebraic number theory.[30]

In Cryptography

Primitive roots modulo nn play a central role in cryptographic protocols that rely on the hardness of the discrete logarithm problem (DLP) in multiplicative groups. In these systems, a primitive root gg generates a cyclic subgroup of order ϕ(n)\phi(n), where ϕ\phi is Euler's totient function, ensuring maximal cycle length and uniform distribution of powers for secure key generation and encryption. This property is particularly exploited when n=pn = p is a large prime, making the group Zp×\mathbb{Z}_p^\times cyclic of order p−1p-1. The Diffie-Hellman key exchange, introduced by Whitfield Diffie and Martin E. Hellman in 1976, uses a primitive root gg modulo a large prime pp to enable two parties to compute a shared secret key K=gabmod  pK = g^{ab} \mod p without transmitting it directly: one party sends gamod  pg^a \mod p after selecting private exponent aa, and the other responds with gbmod  pg^b \mod p using private bb. The choice of gg as a primitive root guarantees that the subgroup spans the full group order p−1p-1, maximizing the key space and resisting certain factoring-based attacks on the DLP. This mechanism underpins secure key agreement in protocols like TLS and IPsec. ElGamal encryption, proposed by Taher ElGamal in 1985, extends this idea for public-key encryption. The recipient generates a key pair with primitive root gg modulo prime pp, private exponent xx, and public key h=gxmod  ph = g^x \mod p. To encrypt message mm, a sender chooses random kk and computes ciphertext (gkmod  p,m⋅hkmod  p)(g^k \mod p, m \cdot h^k \mod p); decryption recovers mm via m=(m⋅hk)⋅(gk)−xmod  pm = (m \cdot h^k) \cdot (g^k)^{-x} \mod p. The primitive root ensures the DLP in ⟨g⟩\langle g \rangle is hard, providing semantic security under the decisional Diffie-Hellman assumption. The Digital Signature Algorithm (DSA), specified in NIST's FIPS 186-4 standard, employs a prime qq dividing p−1p-1 and a generator gg of order qq in Zp×\mathbb{Z}_p^\times (equivalent to a primitive root when q=p−1q = p-1). Signers use private key xx to produce signatures (r,s)(r, s) where r=(gkmod  p)mod  qr = (g^k \mod p) \mod q and s=k−1(H(m)+xr)mod  qs = k^{-1}(H(m) + x r) \mod q for hash H(m)H(m) of message mm and random kk; verification checks gH(m)s−1mod  p=rg^{H(m) s^{-1}} \mod p = r after subgroup projection. This structure leverages the DLP hardness in the order-qq subgroup for unforgeability. The security of these protocols derives from the computational difficulty of the DLP in subgroups generated by primitive roots, where solving gy≡hmod  pg^y \equiv h \mod p for yy requires subexponential time for large prime-order subgroups, thwarting generic attacks like baby-step giant-step (cost p−1\sqrt{p-1}) and index calculus. Using prime qq near pp mitigates the Pohlig-Hellman algorithm, which reduces DLP security to the largest prime factor of the group order. However, quantum algorithms like Shor's threaten this foundation by solving DLP in polynomial time on quantum computers. As of 2025, NIST has addressed these vulnerabilities through post-quantum cryptography standards that diminish reliance on primitive roots and discrete logs. FIPS 203 (ML-KEM, based on CRYSTALS-Kyber) provides key encapsulation for key exchange, replacing Diffie-Hellman; FIPS 204 (ML-DSA, based on CRYSTALS-Dilithium) and FIPS 205 (SLH-DSA, based on SPHINCS+) offer digital signatures supplanting DSA; and HQC was selected in March 2025 as a backup encryption mechanism. These lattice- and hash-based algorithms ensure quantum resistance without cyclic group structures.

References

  1. [PDF] PRIMITIVE ROOTS: A SURVEY - Dartmouth Mathematics
  2. [PDF] Math 580/780I Notes 14
  3. [PDF] Primitive Roots Modulo Prime Powers - Trinity University
  4. [PDF] 3 Primitive Roots, Indices and the Discrete Logarithm
  5. [PDF] Math 3110: Existence of Primitive Roots
  6. [PDF] Cyclic Groups and Primitive Roots - Trinity University
  7. [PDF] Contents 2 Modular Arithmetic in Z - Evan Dummit
  8. [PDF] 6.8. Primitive Roots and Card Shuffling
  9. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_(Poritz
  10. Totient Function -- from Wolfram MathWorld
  11. Primitive Root -- from Wolfram MathWorld
  12. Multiplicative Order -- from Wolfram MathWorld
  13. primitive root - PlanetMath.org
  14. Disquisitiones arithmeticae : Gauss, Carl Friedrich, 1777-1855
  15. 10.4 Prime Numbers Have Primitive Roots
  16. https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Elementary_Number_Theory_(Raji
  17. 10.3When Does a Primitive Root Exist?¶ permalink
  18. [PDF] Notes for Lecture 15 | Armin Straub
  19. [PDF] Constructing the Primitive Roots of Prime Powers - arXiv
  20. [PDF] Primitive Roots mod p
  21. [PDF] 1 Order
  22. [PDF] Math 580/780I: Test 3, Fall 2010
  23. [PDF] Primitive Roots - UBC Math
  24. Section 10.3: When is There a Primitive Root?
  25. A001918 - OEIS
  26. Artin's Conjecture -- from Wolfram MathWorld
  27. 5.3: Primitive Roots - Mathematics LibreTexts
  28. [PDF] Primitive Roots (Prime Powers), Index Calculus, Lecture 8 Notes
  29. [PDF] Cyclotomic Polynomials and Primitive Roots - garsia at york
  30. [PDF] ARTIN'S PRIMITIVE ROOT CONJECTURE - a survey -
  31. [PDF] Elementary Number Theory: Primes, Congruences, and Secrets
  32. Primitive Root - Algorithms for Competitive Programming
  33. [PDF] Searching for Primitive Roots in Finite Fields - Victor Shoup
  34. [PDF] Finding Primitive Roots Pseudo-Deterministically
  35. [PDF] Discrete logarithms in finite fields and their cryptographic significance
  36. Primitive Roots and a Test for Primality - SpringerLink
User Avatar
No comments yet.