93
$\begingroup$

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

Thanks

  • 0
    @Vadim: Indeed. Thanks.2012-04-19

3 Answers 3

105

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.

3

You could pick the candidates randomly. If p >= 3 and p-1 is therefore even, x^2 modulo p cannot be a primitive root, and if x^3 modulo p is a primitive root then so is x. 1 cannot be a primitive root. That removes 1, 4, 8, 9 and others. I think composite numbers are a bit less likely to be primitive roots when their factors aren't (someone will know the details).

Since you can store quite large powers of small primes in a table, calculating their powers will be a little bit faster. So I'd check small primes first. Just because it is a tiny bit faster. For p = 761, a lot faster.

Obvious question: Does every prime p >= 3 have a prime number as a primitive root? Is that hard to prove?

3

Let $p$ be an odd prime number. If $p-1$ is divisible by $4$ and $a$ is a primitive element then $p-a$ is also primitive. For example $761-6=755$ is primitive because $760$ is divisible by $4$.

  • 3
    This can be proved as follows. Let $p$ be a prime with $p\equiv 1\pmod4$, and let $g$ be a primitive root modulo $p.$ Then $-1\equiv g^{\frac{p-1}{2}}\pmod p,$ so $-g\equiv g^{\frac{p+1}{2}}\pmod p.$ Since $\frac{p+1}{2}$ is prime to $p-1,$ $-g$ is also a primitive root modulo $p.$2016-04-16