Mathematica's PrimitiveRoot[] FunctionDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/