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 is a prime number, there exist primitive roots modulo
. 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
, 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 , let
be the set
. Let
be the set of all numbers
in
that is relatively prime to
. Euler’s phi function
is the count of the elements in the set
. Euler’s theorem states that for any
,
.
Euler’s theorem establishes a solution for the congruence equation where
is a positive integer. Whenever
is the smallest positive solution to
, the number
is said to be a primitive root modulo
.
In general, the smallest positive solution to the equation is called the order of
modulo
. Thus, in terms of the notion of order, any number
is a primitive root modulo
whenever the order of
and
coincide.
__________________________________________________________________________________________________________________
Finding One Primitive Root
For the modulus ,
and
. So
. According to Euler’s theorem,
for all
.
Obviously can never be a primitive root. Thus candidates for primitive roots are the
numbers in the set
. As we will see below, we only need to find one primitive root
from this list. Our plan is to find the smallest primitive root
from this list.
Since , showing that
is a primitive root modulo
requires verifying that
for each
. We can get by with less computation.
If is the smallest positive integer solution to
, then
(see Theorem 4 and Corollary 5 in the post Defining Primitive Root).
So the order of a number can only be the numbers
in the set
that are divisors of
. If
for all such
, then the number
is a primitive root modulo
. If
for one such
, then the number
is not a primitive root modulo
. This is the approach we take to find one primitive root modulo
.
Note that , which has eleven divisors that are less than
. They are:
We start with and check
where
is from the above list of divisors. The first
where
for all eleven
is a primitive root.
We have the following calculation:
So are not primitive root modulo
. For
,
for all eleven
. Thus
is the smallest primitive root modulo
.
__________________________________________________________________________________________________________________
Finding the Other Primitive Roots
If there is one primitive root for a modulus , there are exactly
many primitive roots (see Corollary 7 in the post Defining Primitive Root). For the modulus
, there are
primitive roots.
Theorem 6 in that same post says that if is a primitive root modulo
, then
(or the least residue of it) is also a primitive root for all integers
that are relatively prime to
.
So in this example, for the exponents we only need to find the numbers in the set that are relatively prime to
.
To find the numbers that are relatively prime to
, we can list out the numbers
. Since the prime factors of
are
, we cross out the multiples of
, the multiples of
, and finally the multiples of
. The following matrix shows the
numbers that remain.
From the last section, we know that is a primitive root modulo
. For each number
in the above matrix, we calculate the least residue of
modulo
. The following shows the results.
For example, the following calculation gives the ten results in the first row of the above matrix.
The following matrix shows the primitive roots sorted in increasing order.
__________________________________________________________________________________________________________________
Exercise
We leave with an exercise (for any interested reader).
Find all the primitive roots modulo . Answers are show below.
The algorithm demonstrated here is further described in An elementary algorithm for finding primitive roots.
___________________________________________________________________________________________________________________
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)