Finding a primitive root of a prime number

How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?



There is no general formula to find a primitive root. Typically, what you do is you pick a number and test. Once you find one primitive root, you find all the others.

How you test

To test that a is a primitive root of p you need to do the following. First, let s=\phi(p) where \phi() is the Euler’s totient function. If p is prime, then s=p-1. Then you need to determine all the prime factors of s: p_1,\ldots,p_k. Finally, calculate a^{s/p_i}\mod p for all i=1\ldots k, and if you find 1 among residuals then it is NOT a primitive root, otherwise it is.

So, basically you need to calculate and check k numbers where k is the number of different prime factors in \phi(p).

Let us find the lowest primitive root of 761:

  • s=\phi(761)=760=2^3\times5\times19
  • the powers to test are: 760/2=380, 760/5=152 and 760/19=40 (just 3 instead of testing all of them)
  • test 2:
    • 2^{380}\equiv 1\mod 761 oops
  • test 3:
    • 3^{380}\equiv -1\mod 761 OK
    • 3^{152}\equiv 1\mod 761 oops
  • test 5 (skip 4 because it is 2^2):
    • 5^{380}\equiv 1\mod 761 oops
  • test 6:
    • 6^{380}\equiv -1\mod 761 OK
    • 6^{152}\equiv 67\mod 761 OK
    • 6^{40}\equiv -263\mod 761 hooray!

So, the least primitive root of 761 is 6.

How you pick

Typically, you either pick at random, or starting from 2 and going up (when looking for the least primitive root, for example), or in any other sequence depending on your needs.

Note that when you choose at random, the more prime factors are there in \phi(p), the less, in general, is the probability of finding one at random. Also, there will be more powers to test.

For example, if you pick a random number to test for being a primitive root of 761, then the probability of finding one is roughly \frac{1}{2}\times\frac{4}{5}\times\frac{18}{19} or 38%, and there are 3 powers to test. But if you are looking for primitive roots of, say, 2311 then the probability of finding one at random is about 20% and there are 5 powers to test.

How you find all the other primitive roots

Once you have found one primitive root, you can easily find all the others. Indeed, if a is a primitive root mod p, and p is prime (for simplicity), then a can generate all other remainders 1\ldots(p-1) as powers: a^1\equiv a,a^2,\ldots,a^{p-1}\equiv 1. And a^m \mod p is another primitive root if and only if m and p-1 are coprime (if \gcd(m,p-1)=d then (a^m)^{(p-1)/d}\equiv (a^{p-1})^{m/d}\equiv 1\mod p, so we need d=1). By the way, this is exactly why you have \phi(p-1) primitive roots when p is prime.

For example, 6^2=36 or 6^{15}\equiv 686 are not primitive roots of 761 because \gcd(2,760)=2>1 and \gcd(15,760)=5>1, but, for example, 6^3=216 is another primitive root of 761.

Source : Link , Question Author : Community , Answer Author : Vadim

Leave a Comment