Finding Primitive Roots

In the previous post called Defining Primitive Root, we define and discuss the notion of primitive roots and prove some elementary theorems. In this post we use these theorems to find primitive roots modulo a prime number. The algorithm demonstrated here is further described in An elementary algorithm for finding primitive roots.

It is a theorem that if the modulus m is a prime number, there exist primitive roots modulo m. But the theorem does not provide an algorithm of how to find one. We demonstrate a process of how to find all the primitive roots of a prime modulus. We use the prime modulus m=277, a number that is small enough to make the calculation not too lengthy and is big enough to make the demonstration meaningful.

The modular arithmetic calculation discussed below can be programmed in a computer or done using a hand-held calculator using the fast powering algorithm (which is discussed in this post).

__________________________________________________________________________________________________________________

Background

For any positive integer m, let \mathbb{Z}_m be the set \left\{0,1,2,\cdots,m-1 \right\}. Let (\mathbb{Z}_m)^* be the set of all numbers a in \mathbb{Z}_m that is relatively prime to m. Euler’s phi function \phi(m) is the count of the elements in the set (\mathbb{Z}_m)^*. Euler’s theorem states that for any a \in (\mathbb{Z}_m)^*, a^{\phi(m)} \equiv 1 \ (\text{mod} \ m).

Euler’s theorem establishes a solution for the congruence equation a^{x} \equiv 1 \ (\text{mod} \ m) where x is a positive integer. Whenever \phi(m) is the smallest positive solution to a^{x} \equiv 1 \ (\text{mod} \ m), the number a is said to be a primitive root modulo m.

In general, the smallest positive solution to the equation a^{x} \equiv 1 \ (\text{mod} \ m) is called the order of a modulo m. Thus, in terms of the notion of order, any number a \in (\mathbb{Z}_m)^* is a primitive root modulo m whenever the order of a and \phi(m) coincide.

__________________________________________________________________________________________________________________

Finding One Primitive Root

For the modulus m=277, \mathbb{Z}_m=\left\{0,1,2,\cdots,276 \right\} and (\mathbb{Z}_m)^*=\left\{1,2,3,\cdots,276 \right\}. So \phi(277)=276. According to Euler’s theorem, a^{\phi(m)}=a^{276} \equiv 1 \ (\text{mod} \ 277) for all a \in (\mathbb{Z}_m)^*=\left\{1,2,3,\cdots,276 \right\}.

Obviously a=1 can never be a primitive root. Thus candidates for primitive roots are the 275 numbers in the set \left\{2,3,\cdots,276 \right\}. As we will see below, we only need to find one primitive root a from this list. Our plan is to find the smallest primitive root a from this list.

Since a^{\phi(m)}=a^{276} \equiv 1 \ (\text{mod} \ 277), showing that a is a primitive root modulo m=277 requires verifying that a^j \not \equiv 1 \ (\text{mod} \ 277) for each j \in \left\{2,3,\cdots,275 \right\}. We can get by with less computation.

If x=k is the smallest positive integer solution to a^{x} \equiv 1 \ (\text{mod} \ m), then k \ \lvert \ \phi(m) (see Theorem 4 and Corollary 5 in the post Defining Primitive Root).

So the order of a number a can only be the numbers j in the set \left\{2,3,\cdots,275 \right\} that are divisors of \phi(277)=276. If a^j \not \equiv 1 \ (\text{mod} \ 277) for all such j, then the number a is a primitive root modulo m=277. If a^j \equiv 1 \ (\text{mod} \ 277) for one such j, then the number a is not a primitive root modulo m=277. This is the approach we take to find one primitive root modulo m=277.

Note that 276=2^2 \cdot 3 \cdot 23, which has eleven divisors that are less than 276. They are:

    \displaystyle \begin{aligned} \text{divisors of } 276&=1 \\&=2 \\&=3 \\&=4 \\&=6 \\&=12 \\&=23 \\&=46 \\&=69 \\&=92 \\&=138 \end{aligned}

We start with a=2 and check a^j where j is from the above list of divisors. The first a where a^j \not \equiv 1 \ (\text{mod} \ 277) for all eleven j is a primitive root.

We have the following calculation:

    2^{92} \equiv 1 \ (\text{mod} \ 277)

    3^{69} \equiv 1 \ (\text{mod} \ 277)

    4^{46} \equiv 1 \ (\text{mod} \ 277)

So a=2,3,4 are not primitive root modulo m=277. For a=5, a^j \not \equiv 1 \ (\text{mod} \ 277) for all eleven j. Thus a=5 is the smallest primitive root modulo m=277.

__________________________________________________________________________________________________________________

Finding the Other Primitive Roots

If there is one primitive root for a modulus m, there are exactly \phi(\phi(m)) many primitive roots (see Corollary 7 in the post Defining Primitive Root). For the modulus m=277, there are \phi(\phi(277))=\phi(276)=88 primitive roots.

Theorem 6 in that same post says that if a is a primitive root modulo m, then a^j (or the least residue of it) is also a primitive root for all integers j that are relatively prime to \phi(m).

So in this example, for the exponents we only need to find the numbers in the set \left\{1,2,3,\cdots,276 \right\} that are relatively prime to \phi(277)=276.

To find the 88 numbers that are relatively prime to \phi(277)=276, we can list out the numbers 1,2,3,\cdots,276. Since the prime factors of 276 are 2,3,23, we cross out the multiples of 2, the multiples of 3, and finally the multiples of 23. The following matrix shows the 88 numbers that remain.

    \displaystyle \begin{bmatrix} 1&5&7&11&13&17&19&25&29&31     \\ 35&37&41&43&47&49&53&55&59&61 \\ 65&67&71&73&77&79&83&85&89&91 \\ 95&97&101&103&107&109&113&119&121&125 \\ 127&131&133&137&139&143&145&149&151&155 \\ 157&163&167&169&173&175&179&181&185&187 \\ 191&193&197&199&203&205&209&211&215&217 \\ 221&223&227&229&233&235&239&241&245&247 \\ 251&257&259&263&265&269&271&275&\text{ }&\text{ }  \end{bmatrix}

From the last section, we know that a=5 is a primitive root modulo m=277. For each number j in the above matrix, we calculate the least residue of 5^j modulo m=277. The following shows the results.

    \displaystyle \begin{bmatrix} 5&78&11&227&135&167&20&44&77&263     \\ 114&80&140&176&31&221&179&43&6&150 \\ 124&53&162&172&24&46&219&212&94&134 \\ 96&184&45&17&99&259&107&180&68&119 \\ 205&151&174&166&272&199&266&50&142&110 \\ 257&233&200&14&163&197&137&101&246&56 \\ 98&234&271&127&153&224&115&105&253&231 \\ 58&65&183&143&181&93&232&260&178&18 \\ 170&97&209&158&72&126&103&111&\text{ }&\text{ }  \end{bmatrix}

For example, the following calculation gives the ten results in the first row of the above matrix.

    5^{1} \equiv 5 \ (\text{mod} \ 277)

    5^{5} \equiv 78 \ (\text{mod} \ 277)

    5^{7} \equiv 11 \ (\text{mod} \ 277)

    5^{11} \equiv 227 \ (\text{mod} \ 277)

    5^{13} \equiv 135 \ (\text{mod} \ 277)

    5^{17} \equiv 167 \ (\text{mod} \ 277)

    5^{19} \equiv 20 \ (\text{mod} \ 277)

    5^{25} \equiv 44 \ (\text{mod} \ 277)

    5^{29} \equiv 77 \ (\text{mod} \ 277)

    5^{31} \equiv 263 \ (\text{mod} \ 277)

The following matrix shows the 88 primitive roots sorted in increasing order.

    \displaystyle \begin{bmatrix} 5&6&11&14&17&18&20&24&31&43     \\ 44&45&46&50&53&56&58&65&68&72 \\ 77&78&80&93&94&96&97&98&99&101 \\ 103&105&107&110&111&114&115&119&124&126 \\ 127&134&135&137&140&142&143&150&151&153 \\ 158&162&163&166&167&170&172&174&176&178 \\ 179&180&181&183&184&197&199&200&205&209 \\ 212&219&221&224&227&231&232&233&234&246 \\ 253&257&259&260&263&266&271&272&\text{ }&\text{ }  \end{bmatrix}

__________________________________________________________________________________________________________________

Exercise

We leave with an exercise (for any interested reader).

Find all the primitive roots modulo m=127. Answers are show below.

\text{ }

\text{ }

\text{ }

\text{ }

    \displaystyle \begin{bmatrix} 3&6&7&12&14&23&29&39&43&45     \\ 46&48&53&55&56&57&58&65&67&78 \\ 83&85&86&91&92&93&96&97&101&106 \\ 109&110&112&114&116&118&\text{ }&\text{ }&\text{ }&\text{ }  \end{bmatrix}

The algorithm demonstrated here is further described in An elementary algorithm for finding primitive roots.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements

One thought on “Finding Primitive Roots

  1. In trying to figure out how to derive full period multipliers for a Lehmer generator to use in a crypto project, I came across this blog and was inspired by your stepwise and clear presentation. Attached please find a link to a primitive root tool which incorporates the algorithm you present here:
    http://waysidehealth.com/mathStuff/primitiveRoots.html
    It’s not written for big integers, so it’s subject to JavaScript overflow constraints (2^53 or so), but it’s useful as a learning tool and certainly solved the problem I started with (I don’t need huge moduli)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s