# Practical method of calculating primitive roots modulo a prime

How are generators of a (large prime) set calculated in popular programs such as pgp and libraries such as java's bouncycastle? i cannot imagine them just churning away at every value between 2 and p until something comes up, but there does not seem to be any description of some other method programmers use to find them.

even if they test every number between 2 and p, what is the test? is it checking if the set generated is {1,2,...p-1}? that seems like it would take too much memory.

can anyone give me some pseudocode on how to do it? im trying something thats probably incredibly naive and the program is using 1.5gb ram after a few seconds, with only a 32 bit value

-
The search term you want is primitive root (en.wikipedia.org/wiki/Primitive_root_modulo_n) (I have edited the title to reflect this so it is more informative; I hope you don't mind). Churning away at every value between $2$ and $p$ is not actually such a bad idea; conditional on the generalized Riemann hypothesis you're guaranteed to find a primitive root between $2$ and $O(\log^6 p)$ (although I have no idea how big the constant is). –  Qiaochu Yuan Jun 9 '12 at 20:12
I suspect the OP's disinclination to check many values is related to the inefficiency of checking each one by the current implementation. –  Erick Wong Jun 9 '12 at 21:53
yeah. more or less, and there's really no good non-super-technical explanation on how to find them (havent checked the links in the answers provided yet) –  calccrypto Jun 10 '12 at 1:44
Enumerating and testing is not a good idea... For cryptographic purposes, $p$ will usually be above $2^{2048}$. –  Jay Nov 9 '12 at 10:12

The basic algorithm for testing whether $a$ is a primitive root mod $p$ is to factor $p-1$ to identify all the prime factors $q \mid p-1$ (there are at most $(1+o(1))\log p$ such factors). If $a$ is not primitive, then its multiplicative order must properly divide $p-1$ and therefore must divide some $(p-1)/q$.

Therefore, you only need to check whether $a^{(p-1)/q} \not\equiv 1 \pmod p$ for all primes $q \mid p-1$. If so, then $a$ is primitive. There is absolutely no need to use gigabytes of RAM to store all the powers of $a$.

As pointed out by Qiaochu Yuan, you should not expect to check many values of $a$ before finding one that is primitive. In fact, you don't need to rely on GRH if you sample purely at random: there are $\phi(p-1)$ primitive roots between $2$ and $p-1$, so you can expect to find one randomly after about $p/\phi(p-1)$ tries. This number is usually very small and it cannot be much larger than $1.78 \log \log p$ even for exceptional values of $p$. So in practice you will never hit the $O(\log^6 p)$ bound before finding a primitive root.

-
Right. So it seems like the main bottleneck here is factoring $p-1$? (Also, the OP should probably be made aware of binary exponentiation (en.wikipedia.org/wiki/Exponentiation_by_squaring) for the purposes of testing whether $a^{(p-1)/q} \not\equiv 1 \bmod p$.) –  Qiaochu Yuan Jun 9 '12 at 22:18
@QiaochuYuan True, that does seem like the most expensive part of this operation. However, it does appear that there are polynomial-time algorithms for probabilistic primitive roots (analogous to probabilistic primes). This paper seems to be a good source. –  Erick Wong Jun 9 '12 at 22:29
Note that this employs the Lucas primality test. See also primality certificates, e.g. Pratt certificates. –  Bill Dubuque Jun 9 '12 at 22:44
thanks, i know about exponentiation by squaring, and im using miller-rabin to test for primality. my main problem with this answer is: factor p−1 to identify all the prime factors q∣p−1. how do i get the factors of some ridiculously large number? :) –  calccrypto Jun 10 '12 at 1:42

As others have mentioned, we don't know efficient methods for finding generators for $(ℤ/pℤ)^∗$ without knowing the factorization of $p-1$. However, you can efficiently generate a random factored number $n$, then test if $n+1$ is prime, and then compute primitive roots modulo $n+1$. See Victor Shoup -- A Computational Introduction to Number Theory and Algebra, chapter 11. (You actually need sections 11.1 about finding generators, 9.6 for generating random factored numbers and 9.5, for generating a random non-increasing sequence).

-

This is, as you know a very hard problem. Strictly speaking you wouldn't need to check through the entire set as you know if $2$ isn't a primitive root then $4$ isn't one either and so on. So you can look through the "usual suspects" (ie $2,3,5,$ etc) and use binary exponentiation to cut down on the time complexity

William Stein has a webpage on the problem of finding generators for $(\mathbb{Z}/p\mathbb{Z})^*$. The method given is not very useful however as it requires knowing the factorization of $p-1$ which, currently, is a problem in $NP$.

There are some probabilistic polytime algorithms for finding primitive roots that a lot faster than deterministic methods and by repeated testing you can cut down on the chance of error. Also assuming the Extended Riemann Hypothesis, there are deterministic polytime algorithms.

However in general no efficient (fast) deterministic algorithm is known.

-
The polytime algorithms link (the second one) is broken. –  Brandon Carter Jun 10 '12 at 0:26
@BrandonCarter Thanks. I "unbroke" it. –  Eugene Jun 10 '12 at 0:28
on Stein's page, what is that magical black box that gives me the prime factors of a 2048 bit value?. i guess, since p is prime, p-1 is even, so 2 * (p-1)/2, but then what? –  calccrypto Jun 10 '12 at 1:51
Right now I believe the fastest "magical box" is the number field sieve method. Once quantum computers come into play we have Shor's Algorithm. –  Eugene Jun 10 '12 at 1:53
This NFS is "fastest" when we aren't considering a Mersenne prime. If it is a Mersenne prime then I think Lucas-Lehmer is better. –  Eugene Jun 10 '12 at 1:58

I don't know what the precise algorithm is, but perhaps they have routines and subroutines to work with. For example, clearly quadratic residues must be ruled out, so we're left with only half the elements in $\,\left(\mathbb{F}_p\right)^*\,$.

Next, perhaps they check whether $\,\displaystyle{a^{\frac{p-1}{2}}}=-1\,$ from the remaining elements, as the primitive roots will pop up from these elements...

-