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

Skip to content
# Finding a primitive root of a prime number

## The Question :

*104 people think this question is useful*
*The Question Comments :*
## The Answer 1

*118 people think this answer is useful*
## The Answer 2

*4 people think this answer is useful*
## The Answer 3

*3 people think this answer is useful*
## The Answer 4

*0 people think this answer is useful*

## The Answer 5

*0 people think this answer is useful*

2021-01-06

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

- Finding primitive roots is generally difficult. For $761$, there are exactly $\phi(\phi(761)) = \phi(760) = \phi(2^3\times 5\times 19) = 2^2\times 4\times 18 = 288$ primitive roots, so you have about a 3/8 change of picking a primitive root by picking one at random. So pick one at random and check to see if $a^{380}\equiv -1\pmod{761}$; if yes, then $a$ is a primitive root; if not, then pick something else.
- A given $a$ is a primitive root modulo $761$ if and only if the order of $a$ modulo $761$ is
*exactly*$760$. Since $761$ is prime, there are only two elements whose square is $1$: $1$ and $-1$. Since $a^{760}\equiv 1\pmod{761}$ (Fermat’s Little Theorem), we know that $a^{380}\equiv 1$ or $a^{380}\equiv -1$. In the former case, the order of $a$ divides $380$, so $a$ is not a primitive root. In the latter case, the smallest $k$ such that $a^k\equiv1\pmod{761}$ is $760$, so $a$ is in fact a primitive root. So all you need to do is compute $a^{380}\bmod 761$. - Wolfram Alpha says that 6 is the smallest primitive root of 761.
- @Arturo This is a necessary condition, but not sufficient. 🙁
- @Arturo I have posted my answer below, and among other things, I have an example of why just testing $a^{380}$ is not enough to say that $a$ is a primitive root. See what happens to $3$ when you test it against $761$: $3^{380}\equiv -1\mod 761$, but, in fact, $3^{380/5}=3^{76}\equiv -1\mod 761$ as well, and $3^{152}=1\mod 761$. This is precisely why you need to test all the powers: $760/2$, $760/5$ and $760/19$. In fact, when you test $3$ only power $152$ (among the three powers above) will tell you that it is not a primitive root, when you test 35 — only 40, and when test 2 — only 380.

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.