Finding a primitive root of a prime number

Solution 1:

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.

Solution 2:

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$.

Solution 3:

You could pick the candidates randomly. If $p \ge 3$ and $p-1$ is therefore even, $x^2 (\text{mod } p)$ cannot be a primitive root, and if $x^3 (\text{mod } 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.

The obvious question: Does every prime $p \ge 3$ have a prime number as a primitive root? Is that hard to prove?

Solution 4:

Building on Vadim's answer, we can cut down on the required powers by assessing whether a residue is quadratic, without using the power calculation. Thereby the highest power we would have to calculate is eliminated from having to use the direct calculation.

• To test $2$, check the residue of the prime modulus $p$ you're considering $\bmod 8$. $2$ would be a quadratic residue, therefore not primitive, if and only if $p\in \{1,7\}\bmod 8$.

• To test an odd prime, use quadratic reciprocity to simplify.

• To test a squarefree product (all other composites are trivial), count the number of its prime factors that turned out to be nonquadratic residues. This count must be odd for a primitive root.

Let's try these methods with $761$:

• $2$ is a quadratic residue because $761\equiv1\bmod 8$. This kills $2$ as a potential primitive root.

• $3$ gives, by QR, $(3|761)=(761|3)=(2|3)=-1$, so we have a nonquadratic residue -- cheers! We would still have to test for a higher-power residue, and Vadim's calculation of $3^{152}$ reveals a fifth-power residue instead of a primitive root.

• $5$ gives $(5|761)=(761|5)=+1$, a quadratic residue. Move along.

• $6=2×3$ is a squarefree product in which one factor ($3$) is nonquadratic and the other ($2$) is quadratic. Thus an odd nonquadratic-residue count. So $6$ is a nonquadratic residue and we test it for a higher power resudue. Vadim's calculations of $6^{152}$ and $6^{40}$ eliminate these pitfalls and thus $6$ is rendered a primitive root.