Practical method of calculating primitive roots modulo a prime

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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