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.

Thanks in advance,
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,

Although Dr. Schwa addressed your original question, I wanted to write 
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 
researching the literature.  For more information, refer to

   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/