Associated Topics || Dr. Math Home || Search Dr. Math

### Mathematica's PrimitiveRoot[] Function

```Date: 11/14/2002 at 00:28:59
From: Harry
Subject: Unprovable primitive root

Dear Dr. Math,

My current project is to develop a fast primitive root finder. It is
still currently only 32 bits. My problem is that it is difficult to
find the primitive root of some primes, even when the total primitive
root is in theory large enough and it should not be a problem to find
one.

Example: p = 4294967291 ((2^32) - 5). Its p-1 factors are:

2, 5, 19, 22605091.

The total primitive root is:

phi(phi(p)) = 1 * 4 * 18 * 22605090 = 1627566480

The ratio is (roughly) 3:1 (4294967291:1627566480), meaning that
average of 3 integer values, 1 must be primitive root, but I have
tried to find one to no avail.

It seems strange that we can calculate and prove (testing with small
primes only) that we can find all the primitive roots of a prime =
phi(phi(a)), but we cannot find its primitive root without randomly
testing each candidate.

Another thing is that some sites say that a perfect power value,
e.g.: 4, 8, 9, 16, 25, 27, 32, 36, etc., can not be a primitive root,
but this is wrong, isn't it? Prove:

8 is primitive root of 29, 53, 59, 83, etc.
27 is primitive root of 53, 89, etc.
32 is primitive root of 59, 67, 83, etc.

After we find one primitive root, what is the next primitive root?
Is there any formula for this? I could not find any pattern from the
primitive root table.

If you give an example, please use 4294967291 as the prime or tell me
that number is NOT prime.

Hariyanto Lim
```

```
Date: 11/14/2002 at 03:38:22
From: Doctor Schwa
Subject: Re: Unprovable primitive root

I just started Mathematica and said MultiplicativeOrder[2,2^32-5]
and it returned 4294967290, which I think means it's a primitive root.

6 again seems to be a primitive root. I get:

2, 6, 8, 10, 14, 19, 26, 29, 34, 37, 42, 43, 46, 47

as the primitive roots that are less than 50. But I don't think the
job of finding a primitive root is an easy one!

>Another thing is that some sites define that a perfect power value,
>eg: 4, 8, 9, 16, 25, 27, 32, 36, etc. can not be a primitive root,
>but this is wrong, isn't it?

I've never heard of this idea. Of course prime powers can be primitive
roots.

Once you find one primitive root, a, then a^(any power relatively
prime to phi(m)) will also be a primitive root mod m.

In your example, since phi(2^32-5) = 2^32-6, which factors as
2*5*19*22605091, and 2 is a primitive root, 2^3, 2^7, 2^9, and so on
(2^ any power not divisible by 2, 5, 19, or that big number) will all
be primitive roots as well.

For further reading see Eric Weisstein's World of Mathematics:

Primitive Root
http://mathworld.wolfram.com/PrimitiveRoot.html

Let me know if there's anything else I can do to help.

- Doctor Schwa, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 11/14/2002 at 23:32:43
From: Doctor Pete
Subject: Re: Unprovable primitive root

Hi Harry,

you regarding Mathematica's PrimitiveRoot[] function.

First of all, PrimitiveRoot[] uses the following definition of a
primitive root:

Let n be a positive integer. Then g is a primitive root of n if g has
order phi(n) modulo n, or equivalently, g^(phi(n)) == 1 (mod n), but
g^k !== 1 (mod n) for all positive integers k < phi(n).

Clearly, this definition is a generalization of the case when n is
prime, in which case phi(n) = n-1.

The reason for this generalization is that we are in some sense
preserving the essential idea of a primitive root and extending its
existence to a larger class of numbers - in particular, to numbers of
the form n = p^a or 2p^a, for primes p. In the generalized case, we
can't hope to generate all values mod n, and so in a way what we are
doing is finding a value that generates as many as possible.

Now, since it is mentioned that PrimitiveRoot[] uses FactorInteger[],
it does not necessarily find the complete factorization of n.

Mathematica is finding the generalized primitive root, which exists
for such non-prime values. It will not calculate a primitive root for
composites that are not powers of primes or twice the power of a
prime, as you can read for yourself at In[20]:=.

In the phrase "generator for the group of numbers relatively prime to
n under multiplication modulo n," "generator" refers to an element g
in the group (Z/nZ)^x. The word "multiplication" refers to the group
operation (which is most certainly not exponentiation), which is
"multiplication modulo n."

This might be confusing, so I'll explain it in full detail. We are
looking at a set of integers, say

{0, 1, 2, 3, ..., p-1},  p prime,

and we want to define multiplication on these integers in such a way
that the product of any two elements in this set is also in the set.
Since p is prime, this is easy; for any two elements a, b in this set,
we simply define the product ab to be the product modulo p. So for
example,

{0, 1, 2, 3, 4, 5, 6},

2*3 = 6, but we also have 4*5 = 0, because 4*5 = 20 == 6 (mod 7).  So
the binary operation on this set that makes it a group is called
"multiplication modulo p."  It is not just plain multiplication,
because then one would obtain numbers not in the original set, e.g.,
20.

Thus, we have a set and a binary operation on that set which induces a
group structure. The identity is 1, and it is not hard to see that an
inverse exists for every element, because we can always find a number
b such that ab == 1 (mod p) for any element a.

We call the resulting group (Z/pZ)^x, written with a superscript times
symbol, to indicate the group of integers under multiplication modulo
p. It is also called the multiplicative group of integers mod p. We
distinguish this from the additive group of integers mod p, written
(Z/pZ)^+ (superscript plus symbol), in which the operation on elements
of the set is addition modulo p.

A primitive root g is an element that generates the group (Z/pZ)^x,
which means that if you compute g, g^2, etc., you will obtain the
entire set of numbers from 0 to p-1. This is the "traditional"
definition of a primitive root.

But what if we want to consider groups that do not have prime order,
namely the generalization (Z/nZ)^x ? For instance, we might want to
try to define multiplication modulo 8 for a set of size 8,

{0, 1, 2, 3, 4, 5, 6, 7},

but this is impossible because inverses do not always exist: There is
no element b such that 4b == 1 (mod 8), for instance. If you are
familiar with multiplicative inverses modulo a composite number, then
you would know that the only way to do this is to include only those
elements that are relatively prime to the modulus, namely

{1, 3, 5, 7}

and then define the group operation as multiplication modulo 8.
Similarly, the group (Z/10Z)^x is the set {1, 3, 7, 9}, with group
operation multiplication modulo 10.  The order of the group is simply
phi(10) = 4, and a primitive root in this case is a number that is a
generator of this set. So 7 is a primitive root, because

7^1 = 7,
7^2 = 49 == 9,
7^3 == 63 == 3,
7^4 == 21 == 1,

and so 7 "generates" the other elements. But you have to remember that
the group operation is multiplication modulo n, not exponentiation,
even though it may look like it. What's really happening is that we're
just using a shorthand notation when we say something like 7^4, which
really is 7(7(7(7))) (mod 10).

I am not aware of any variant definitions of "primitive root,"
specifically "exponential primitive roots" versus "multiplicative
primitive roots," since the only definition I am aware of is the one
I supplied at the beginning of this message.

You seem interested in random number generation and, more generally,
number theory as it applies to coding theory and perhaps cryptography.
I highly recommend that you study abstract algebra if you wish to
continue in this line of research. You would do well to learn how a
great deal of elementary number-theoretic ideas have their basis in
group theory.

As for your original question of an efficient means of calculating a
primitive root of a number, I do not know of such an algorithm.
There has been much discussion on this very old problem; I suggest

Primitive Root - Eric Weisstein, World of Mathematics
http://mathworld.wolfram.com/PrimitiveRoot.html

to gain a better understanding of primitive roots and their related
concepts.

- Doctor Pete, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search