Return to Answer

If we want a random generator, we can pick a random secret $x$ in $[1,q]$ and use $g$ as follows, after checking $g\ne1$ ($g=1$ is overwhelmingly unlikely):

If we want a random generator, we can pick a random secret $x$ in $[1,q-1]$ and use $g$ as follows:

• for (1.) and $p\bmod8=3$: $g\gets2^{2x+1}$
• for (1.) and $p\bmod8=7$: by trial and error we find $y$ with $y^{(p-1)/2}\bmod p\ne 1$ (equivalently, with $y^{(p-1)/2}\bmod p=p-1$ ); the expected number of attempts is about two if we explore consecutive odd $u$ starting $u=3$; then $g\gets u^{2x+1}$.
• for (2.), $g\gets4^x$
• for (3.), $g\gets2^{(p/q)\,x}$

• for (1.) and $p\bmod8=3$: $g\gets2^{2x+1}$
• for (1.) and $p\bmod8=7$: by trial and error we find $y$ with $y^{(p-1)/2}\bmod p\ne 1$ (equivalently, with $y^{(p-1)/2}\bmod p=p-1$ ); the expected number of attempts is about two if we explore consecutive odd $u$ starting $u=3$; then $g\gets u^{2x+1}$.
• for (2.), $g\gets2^{2x}$
• for (3.), $g\gets2^{((p-1)/q)\,x}$

So we'll be working within the group $\mathbb Z_p^*$, a notation for the subset of the ring $\mathbb Z/p\mathbb Z$ formed by elements that have a multiplicative inverse, which can be shown to form a group. Since $p$ is prime, that group can be assimilated to integers $\{1,2,\ldots,p-2,p-1\}$. It has $p-1$ elements. This group's internal law is multiplication modulo $p$.

For (1.) and (2.), generating $p$ and $q$ boils down to generating prime $q$ with $p=2q+1$ also prime. It's efficient to make a relatively quick test that $q$ is not composite (e.g. a Fermat test to base 2: check that $2^{q-1}\bmod q=1$), then a thorough test that $p=2q+1$ is prime; then a thorough test that $q$ is prime. It can be shown that (for large $q$) it must hold $q\bmod3=2$, and $q\bmod5\in\{1,3,4\}$, thus $q\bmod30\in\{11,23,29\}$, which narrows down the search. Considering more small prime moduli would further narrow search.

So we'll be working within the group $\mathbb Z_p^*$, a notation for the subset of the ring $\mathbb Z/p\mathbb Z$ formed by elements that have a multiplicative inverse, which can be shown to form a group. Since $p$ is prime, $\mathbb Z/p\mathbb Z$ is a field, and $\mathbb Z_p^*$ is that field less the neutral for addition. $\mathbb Z_p^*$ can be assimilated to integers $\{1,2,\ldots,p-2,p-1\}$. It has $p-1$ elements. This group's internal law is multiplication modulo $p$.

For (1.) and (2.), generating $p$ and $q$ boils down to generating prime $q$ with $p=2q+1$ also prime. It's efficient to make a relatively quick test that $q$ is not composite (e.g. a Fermat test to base 2: check that $2^{q-1}\bmod q=1$), then a thorough test that $p=2q+1$ is prime; then a thorough test that $q$ is prime. Further, for a small prime $s$, it holds $q\bmod s\not\in\{0,(s-1)/2\}$. Thus $q\bmod3=2$, $q\bmod5\in\{1,3,4\}$, thus $q\bmod30\in\{11,23,29\}$, which narrows down the search. Considering slightly larger $s$ can be put to use for a sieve or other speedup.