Some tips on how to find primitive roots modulo prime number p.

Problem of finding primitive root modulo prime number p appears in many applications, the most common is cryptography.

I realised during some conversations that programmers who are not after math studies, oten don't do that in optimal way, especially if they study Computer Science or other technical field and need to do that for some project at university and they care mainly about code to be working, not to be working fast. They usually just start searching for roots by checking if 2 is a root, then if 3 is a root, then if 4 is a root (which is nonsense) etc.
Of course I will not prove things because post would be too hard and long, but don't worry, I am honest and will not tell You lies.

First I will go through everything and at the end there will be a summarize.

Recall that x is a primitive root if a set {x mod p, x^{2} mod p,x^{3} mod p,...,x^{p-1} mod p} contains all numbers of set {1,2,...,p-1}.
Of course exponentating x and checking p-1 times if we got number which is not contained in numbers obtained so far is very foolish and inefficient.

First observation is that for primitive root it is mandatory to be quadratic nonresidue modulo p. It means that x^{(p-1)/2} = -1 mod p.
But that condition is not enough generally. For most primes p, not all nonresidues are primitive roots.
But if (p-1)/2 is also a prime number, then every nonresidue modulo p is also a primitive root modulo p. Or, almost every. p-1 is never a primitive root as (p-1)^2 = 1 mod p. p-1 is a
Example: 11 is prime and (11-1)/2 = 5 is prime. Therefore for 11, nonresidues = {2,6,7,8,10} and primitive roots = {2,6,7,8}.
So, for such primes, just check if for x different than p-1, x^{(p-1)/2} = -1 and if yes, x is a primitive root.
I'll remind that checking if natural number is prime is in P class (algorithm AKS) but checking has quite strange implementation.

Unfortunately prime numbers's roots are not such easy visible :(

Next, if k is a square of a natural number, then it is not primitive root for any prime p > k, because square are quadratic residues. So, 4 is not a primitive root modulo any prime number, it is easy to see that 9 also (for p = 3,5,7 check "on hand").

For prime number p, we have (p-1)/2 quadratic residues (QRs) and (p-1)/2 nonresidues (QNs). Their distribution is symmetric or antisimmetric depending on behaviour of p modulo 4.
If p = 4k+1, then QRss and QNs are symmetric with respect to p/2. Therefore, k is QR/QN if and only if (p-k) is.
For p = 4k+3, they are antisimmetric. If k is QR, then (p-k) is QN and vice versa.

Therefore, primes of form 4k+! have the same number of QR and QN in both intervals [1,p/2) and (p/2,p-1] whereas primes of form 4k+3 have more QRs in one of these intervals and more QNs in the other.
Surprisingly, in 1837 Dirichlet showed that ALL primes of form 4k+3 have more QRs in lower interval [1,p/2) and more QNs in upper interval (p/2,p-1].

So, for primes of form 4k+3, it is more natural to search for primitive roots in interval (p/2,p-1], not to check 2,3,5 (4 we already discussed),6,7...
Of course there may be small primitive root as there are nonresidues in smaller interval, but this post is about "average prime numbers", exceptions always can happen.

For example, 2 is a QN for primes of form 8k+1 and 8k+7, so for 50% of primes, because all odd primes are of form 8k+1,8k+3,8k+5 or 8k+7 and all such forms are "asymptotically equal", so primes of form 8k+1 and 8k+7 are kinda 25% + 25% ~~ 50% of primes. And if Artin's Conjecture is true, it is a primitive root for approximately 37% of primes.
Therefore, if prime is of form 8k+1 or 8k+7, 2 has a 75% chance of being a primitive root!
Did I say earlier not to start checking from 2? No. I said not to check 3,4,5,6 if 2 does not work. Checking 2 is VERY good idea if we checked that our prime is of form 8k+1 or 8k+7.
But if it is not, or our prime is in 25% of these primes for which 2 is not root, then dont go for 3,5,6... .

Dirichlet proves also that for primes of form 4k+1, interval [1, p/4) contains more QRs than QNs (and therefore also interval (3p/4, p-1]. So, we expect for most of primitive roots to be in medium (p/4,3p/4) interval.
Dirichlet proved also that for every p (no matter if 4k+1 or 4k+3), interval [1, p/3) contains more QRs than QNs.

Recall that primes of form 4k+1 are also 8k+1 or 8k+5, while 4k+3 are 8k+3 or 8k+7.

Therefore:

• if our prime is 8k+1, start from checking 2 and if You were in 25% of unlucky numbers, then start checking numbers starting from floor(p/3) and go up
• if our prime is 8k+7, check 2 and if it is not root, go to upper half and check p-3,p-4,p-5 etc (p-1 is not root and p-2 is a resiude for such primes)
• if our prime is 8k+3, check p-2,p-3,p-4 etc...
• if our primes is 8k+5, check floor(p/3 +1), floor(p/3 +2)... etc.
• if p-1/2 is a prime, that every nonresidue is root (except p-1)
  if the number is a square, dont check it (doing sqrt on a number is faster than computing it to power (p-1)/2 and moduling p)
• dont count all power x^1,...,x^p-1. Just check if x^{(p+1)/2} is different from all previous. If yes, it is a root as powers of x form a subgroup of cyclic group Zp*. And the order of subgroup always divides order of a group. So if order of a subgroup is greater than order of group /2, then subgroup is a whole group.

Of course what I wrote is far from optimal, but it is still 100x times better than brainless checking powers of 2, then powers of 3, then powers of 4, which is quite popular among students of "anything which is not a math" as these students usually have a lot of hours of linear algebra or math analysis, but not abstract algebra or number theory.

This is quite nice "basic" optimization of finding primitive root. Practically we have hundreds of theorems which help finding primitive roots for primes of specific form. What I wrote in that article is a very good starter.

Photo is free for commercial use photo from pixabay.com

If You would like more math posts, write in comment.

Some links:
Bittrex reflink: https://bittrex.com/Account/Register?referralCode=PSG-PD1-44V
Kanga reflink: https://kanga.exchange/register?refToken=75dea10a-ca18-4319-abed-3cc465224e7d
TreeCard reflink: https://vrlps.co/RaJCjEW/cp
Publish0x reflink: https://www.publish0x.com/?a=oQeZ4EmEbp
Medium: https://maciej-ficek.medium.com/