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

Solution 1:

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

Solution 2:

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.