If the modulus is small and if primitive roots modulo exist, finding primitive roots can be a simple matter. In such cases, we can simply try out all possible candidate primitive roots. For large , there is no easy or simple algorithm for finding primitive roots. In this post, we present a theorem that characterizes primitive roots. If the modulus is such that can be factored completely, this theorem can serve as an algorithm for finding primitive roots. If the modulus is a large number, may be hard to factor completely and the theorem is likely not an efficient algorithm. However, the theorem will still shed some light on the task of finding a primitive root. The discussion found here contains ideas not found in the previous discussion on finding primitive roots (here and here).

**Defining Primitive Roots**

In the discussion that follows, is a positive integer that is used as the modulus in the modular arithmetic, which can be prime or composite. Furthermore, is a positive integer that is relatively prime to ( is coprime to ), meaning that other than the number 1, there is no divisor in common between and .

Let denote the Euler phi function, which represents the number of positive integers not exceeding that are relatively prime to . For example, as the only numbers under 6 that are relatively prime to 6 are 1 and 5. On the other hand, since all 6 positive numbers under 7 are relatively prime to 7. If general, if is prime, .

According Euler’s Theorem (see Theorem 3 here), for any that is relatively prime to the modulus . Suppose that . The number is a primitive root modulo if for all positive . In other words, is a primitive root modulo if the least number such that is . The least such is called the order of modulo . Stated differently, is a primitive root modulo if the order of modulo is .

The notion of primitive root is characterized by the property that taking powers of generates all the positive integers not exceeding that are relatively prime to . More specifically, the number is a primitive root modulo if and only if the set is a complete listing of all positive integers not exceeding that are relatively prime to . Note that each power of is modulo . For a proof of this fact, see Theorem 5 here.

To give a broader context, the set with the modulo arithmetic is called the ring of integers modulo . When the modulus is a prime number, with the modulo arithmetic is called a field, which is a commutative ring in which every non-zero element has a multiplicative inverse. The field is a finite field. Let , which is called the group of units modulo . Thus every element in has a multiplicative inverse when is a prime. When is a primitive root modulo the prime , , through powering, generates all the elements of , i.e., . Finite fields are of fundamental importance in cryptography as well as in mathematics.

One modern application of primitive roots is the notion of discrete logarithm as used in several algorithms in public-key cryptography such as Diffie-Hellman key exchange. Let be a primitive root modulo . Let be a positive integer that is relatively prime to the modulus . According to the property stated in the preceding paragraph, there is some positive integer not exceeding such that . Such a value is called the discrete logarithm of to the base modulo , denoted by , with the modulus omitted. Discrete logarithms can be quickly computed in some special cases or when the modulus is small. However, there is no efficient method for identifying when is large. The security of the algorithms that rely on discrete logarithm rests on the difficulty of finding when the modulus is a large prime.

**More on Primitive Roots**

Before finding primitive roots, it makes sense to know if primitive roots exist for the modulus in question. In general, primitive roots only exist for a limited set of moduli. According to the primitive root theorem, primitive roots exist only for the moduli 2 and 4 and the moduli that are powers of odd primes and those that are twice the powers of odd primes. For example, when the modulus is the product of two distinct prime numbers, there exist no primitive roots. Thus there are no primitive roots for the modulus 15. When the modulus is a prime number, primitive roots exist. Primitive roots can exist for a composite modulus , but only if it is 4 or a power of an odd prime or twice the power of an odd prime. The proof of the primitive root theorem can be found here.

For a modulus that is a prime number, one thing to keep in mind is that all primitive roots are also quadratic nonresidues. Thus, it makes sense to start the primitive root search with a quadratic nonresidue. If the candidate primitive root is a quadratic residue, find another . If is a quadratic nonresidue, then it may or may not be a primitive root and further calculation should be done to confirm.

For a prime modulus , the order of a primitive root is . Recall that is a quadratic residue modulo means that the quadratic congruence equation has solutions in . If the equation has no solutions, then is a quadratic nonresidue modulo . According to Euler’s criterion (see here), for odd prime moduli, a modular exponentiation can determine the quadratic residue or nonresidue status. If , is a quadratic residue modulo . If , is a quadratic nonresidue modulo . Note that for an odd prime modulus , if , then the order of is less than , which means that is not a primitive root modulo . Thus, if is a primitive root modulo the odd prime , it must be the case that . The converse of this statement is not true. See Example 3 below for a counterexample.

**The Search for Primitive Roots**

Suppose is a candidate primitive root for the odd prime modulus . By definition, is a primitive root if is not congruent to 1 for all . If is a large prime, the amount of checking would be prohibitively large. As the following theorem indicates, the number of checks can be greatly reduced.

**Theorem 1**

Let be relatively prime to the modulus that is an odd prime. Then is a primitive root modulo if and only if the following two conditions hold.

- .
- for each prime factor of .

The theorem does limit the search considerably. The number of the modular exponentiations to perform is no longer but is the number of prime factors of . This means that we need to factor completely. Thus, this algorithm is practical only when the prime factors of are small or when the prime is of a special form. To see how Theorem 1 can be applied, consider the following example.

**Example 1**

Consider = 6329 (a prime). Find the first 2 primitive roots modulo 6329.

Note that . The 3 prime factors are 2, 7 and 113. Then the three values for are , and .

The first candidate is = 2. According to Theorem 1, we need to calculate , and modulo 6329. The results are 5674, 2919, 1. The last term is a 1. This clearly shows that 2 is not a primitive root modulo 6329. With being 1, the number 2 is a quadratic residue modulo 6329, which also indicates that 2 is not a primitive root.

Now = 3. The three calculations are , and modulo 6329 with the results being 2177, 2578, 6328. All three are not congruent to 1. Thus 3 is a primitive root modulo 6329 according to Theorem 1. Note that the last value of 6328 is congruent to -1 modulo 6329. Thus, 3 is a quadratic nonresidue modulo 6329.

Now = 5. The three calculations are , and modulo 6329 with the results being 6211, 1, 1. With 2 of the calculations being a 1, 5 is not a primitive root modulo 6329.

The next smallest primitive root modulo 6329 is 12, supported by the calculation , and modulo 6329.

The idea in Theorem 1 can also work for composite moduli for which primitive roots exist. We only need to replace with

**Theorem 2**

Let be relatively prime to the modulus . Then is a primitive root modulo if and only if the following two conditions hold.

- .
- for each prime factor of .

The proof of Theorem 1 is found in the proof section below.

**More Examples**

**Example 2**

In this example, we expand upon Example 1. Once a primitive root is found, other primitive roots can be derived from it. In this example, all primitive roots modulo 6329 can be obtained by taking over all values of is relatively prime to = 6328 (see Theorem 6 here). With = 6329, we have = 2688. Thus, for the prime modulus 6329, there exist 2688 many primitive roots. Two examples: is a primitive root modulo 6329 as is since 5 and 11 are relatively prime to 6328. On the other hand, is not a primitive root modulo 6329 since 21 is not relatively prime to 6328. Note that for even , is not primitive root for sure since = 6328 is even. On the other hand, for odd , is a primitive root only if and = 6328 are relatively prime, meaning that does not have 7 and 113 as prime factors.

Recall that a primitive root through powering can generate all positive numbers not exceeding the prime modulus that are relatively prime to . In this case is a complete listing of the integers . Thus, any number less than the modulus should be a power of 3. For example, let’s look at 5 and 12. We see that and modulo 6329. Note that 5 is not a primitive root and 12 is a primitive root as shown in Example 1. Thus, the discrete logarithm of 5 base 3 is 5432 and the discrete logarithm of 12 base 3 is 5949.

**Example 3**

This example shows that, though primitive roots are quadratic nonresidues, quadratic nonresidues are not necessarily primitive roots. Consider = 29 with . Here’s the breakdown of the primitive roots and non-primitive roots modulo 29.

- Primitive roots: 2, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 27
- Non-primitive roots: 4, 5, 6, 7, 9, 12, 13, 16, 17, 20, 22, 23, 24, 25, 28

All the primitive roots are quadratic nonresidues. There are 12 primitive roots and there are 14 quadratic nonresidues in this example. There are 2 non-primitive roots that are quadratic nonresidues, namely 12 and 17. Note that . Using Euler’s criterion, and . Thus, 12 and 17 are quadratic nonresidues modulo 29. The reason they are not primitive roots is that and . In general, it is possible that but for other prime factor of .

**Example 4**

Find the first primitive root modulo the prime 97. Once the first primitive root is obtained, use it to derive another primitive root and a non-primitive root.

We apply the concept in Theorem 1. With = 97, . Note that and . According to Theorem 1, compute and modulo 97 starting with = 2.

For , the results are 1, 1, 1, -1 modulo 97. This shows that 2, 3, and 4 are not primitive roots modulo 97. Compute , which is 35, not congruent to 1 modulo 97. According to Theorem 1, 5 is a primitive root modulo 97.

Another primitive root is modulo 97 since 11 is not a prime factor of = 98. A non-primitive root is modulo 97 sine 21 is not relatively prime to 98.

**Example 5**

Find the first primitive root modulo the prime 986113.

We find the first quadratic nonresidue and then confirm whether that is a primitive root. If not we find the next quadratic nonresidue and so on. Note that . According to Theorem 1, the relevant exponents are , and . We find the first quadratic nonresidue by evaluating starting with = 2. The calculation shows that for = 2, 3 and 4. However, is congruent to -1 modulo 986113.

We then evaluate and with the results 240267 and 660749, both not congruent to 1. By Theorem 1, the number 5 is a primitive root modulo 986113.

**Example 6**

We now consider a class of prime numbers for which Theorem 1 is an effective approach of primitive root search. A prime number is called a Sophie Germain prime if is also a prime number. Thus, the definition of Germain prime refers to a pair of prime numbers where the second term in the pair is twice the first term plus one. The first term is called a Sophie Germain prime in honor the French mathematician Sophie Germain (1776-1831) and the second term is called a safe prime. For a safe prime , the factorization of is completely known, which is . To check whether the primitive root candidate is a primitive root modulo the safe prime , we only need to check two exponentiations – and modulo . If both are not congruent to 1, then is a primitive root modulo . In fact, we only need to check . Because is a prime number, there are no non-trivial square roots of 1 modulo .

Based on the preceding paragraph, we know this fact about a safe prime where is the corresponding Sophie Germain prime with . With the exception of modulo , if is a quadratic residue modulo , then it is a primitive root modulo . This gives a clear algorithm for finding a primitive root modulo a safe prime . To determine whether is a primitive root modulo , check whether is a quadratic residue modulo . If it is, then it is not a primitive root. It is a quadratic residue modulo , then it is a primitive root. We can apply the Euler criterion to check for quadratic residue by raising to the power of the Sophie Germain prime modulo .

An example of a Sophie Germain prime is = 1,889 with the associated safe prime = 3,779. Note that . This shows that 2 is a primitive root modulo 3,779.

For a larger example, let = 581,485,876,661, a Sophie Germain prime. The associated safe prime is = 1,162,971,753,323. To see whether 2 is a primitive root modulo , compute modulo , which is -1. Thus 2 is a primitive root modulo .

**The Proof of Theorem 1**

We prove Theorem 1. The proof for Theorem 2 is essentially the same with replaced by .

One direction is clear from definition. If is a primitive root modulo , then and is not 1 for any smaller than .

To prove the other direction, let be relatively prime to . Let where are the prime factors of and each exponent . For each , let . The two conditions in the hypothesis in the theorem are:

Let be the order of modulo , i.e., is the smallest positive integer such that . We know that divides . On the other hand, does not divide for all . If it does divide , we have , against the the second condition in the hypothesis.

Since divides , we can write where for each . Consider the ratio , which is not an integer since does not divide .

If , then would divide . Thus, . Note that . If , we have . This implies that . By the same argument, we have for all . It follows that , i.e., the order of is , showing that must be a primitive root modulo .

Daniel Ma primitive root

Dan Ma primitive root

2022 – Dan Ma