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?

Thanks

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.

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

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?

Finding a primitive root of unity for $\text{modulo-}761$.

For computing purposes, create/calculate the $\text{powers of } 2 \text{ table}$ with 95 rows and 4 columns shown in the second section, corresponding to the subgroup generated by $[2]$; the table contains $378$ elements, missing only $[1]$ and $[760]=[-1]$ from the subgroup.

From the last row of table , where duplicates (two, $[722]$ and $[39]$) are first detected by the computing algorithm,

$\tag 1 \Large2^{-95} \equiv -2^{95} \pmod{761}$

and therefore the order of $[2]$ is $380$ and $[2]$ is not a primitive root of unity.

The number $[3]$ is not in the table but (from the $65^{th}$ row),

$\tag 2 \Large2^{65} \equiv 3^{2} \pmod{761}$

The order of $[2^{65}]$ is $76$ and the order of $[3]$ is $152$ (see this) and
$[3]$ is not a primitive root of unity.

The number $[4]$ is in the table (on the $2^{nd}$ row) and therefore can’t be a primitive root of unity.

The number $[5]$ is in the table (on the $50^{th}$ row, $\,\large 2^{-50} = 5$) and therefore
can’t be a primitive root of unity.

The number $[6]$ is not in the table but (from the $67^{th}$ row),

$\tag 3 \Large2^{67} \equiv 6^2 \pmod{761}$

The order of $[2^{67}]$ is $380$ and the order of $[6]$ is $760$ and $[6]$ is a primitive root of unity.

$\quad \small 2^n \;\,\, 2^{-n} \quad\; -2^n \, -2^{-n}$

002 381     759 380
004 571     757 190
008 666     753 095
016 333     745 428
032 547     729 214
064 654     697 107
128 327     633 434
256 544     505 217
512 272     249 489
263 136     498 625
526 068     235 693
291 034     470 727
582 017     179 744
403 389     358 372
045 575     716 186
090 668     671 093
180 334     581 427
360 167     401 594
720 464     041 297
679 232     082 529
597 116     164 645
433 058     328 703
105 029     656 732
210 395     551 366
420 578     341 183
079 289     682 472
158 525     603 236
316 643     445 118
632 702     129 059
503 351     258 410
245 556     516 205
490 278     271 483
219 139     542 622
438 450     323 311
115 225     646 536
230 493     531 268
460 627     301 134
159 694     602 067
318 347     443 414
636 554     125 207
511 277     250 484
261 519     500 242
522 640     239 121
283 320     478 441
566 160     195 601
371 080     390 681
742 040     019 721
723 020     038 741
685 010     076 751
609 005     152 756
457 383     304 378
153 572     608 189
306 286     455 475
612 143     149 618
463 452     298 309
165 226     596 535
330 113     431 648
660 437     101 324
559 599     202 162
357 680     404 081
714 340     047 421
667 170     094 591
573 085     188 676
385 423     376 338
009 592     752 169
018 296     743 465
036 148     725 613
072 074     689 687
144 037     617 724
288 399     473 362
576 580     185 181
391 290     370 471
021 145     740 616
042 453     719 308
084 607     677 154
168 684     593 077
336 342     425 419
672 171     089 590
583 466     178 295
405 233     356 528
049 497     712 264
098 629     663 132
196 695     565 066
392 728     369 033
023 364     738 397
046 182     715 579
092 091     669 670
184 426     577 335
368 213     393 548
736 487     025 274
711 624     050 137
661 312     100 449
561 156     200 605
361 078     400 683
722 039     039 722

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 primituve root.