Find the generators of multiplicative group of units efficiently?

Question

Say you're give some prime numbers $p_{1},p_{2},p_{3}, p = 2p_{1}p_{2}p_{3} + 1$ (which is assumed to be also prime) and a list of numbers $L$ and you're asked to find the generators of the multiplicative group of units of $Z_p$.

What would be an efficient way to do so?

This question comes from a cryptography course so that the prime numbers are really big and also the list of numbers is formed by big numbers so that I'm having trouble to apply this kind of method.

Answer 1

For any $g$ in the set $\mathbb Z_p^*=\{1,2,\dots,p-1\}$, consider the function $F_g$ over that set defined by $F_g(x)\;=\;g\cdot x\bmod p$. Since $p$ is prime, by Fermat's little theorem, iterating $F_g$, starting from $1$, $p-1$ times, cycles back to $1$.

By definition, $g$ is a generator of $\mathbb Z_p^*$ if and only if that cycling does not occur before these $p-1$ iterations. The smallest $k>0$ where the cycling occurs divides $p-1$ (that $k$ is the order of $g$). Proof sketch: if that $k$ did not divide $p-1$, $k'=(p-1)\bmod k$ would be a smaller $k'>0$ for which the cycling occurs.

It follows that we can test if some $g$ not divisible by $p$ is a generator of $\mathbb Z_p^*$ by checking if $g^k\bmod p\ne1$, with $k=(p-1)/q$ for $q$ each of the distinct prime factors of $p-1$.

Here, for $g$ each of the integers in list $L$, we check if $g\bmod p\ne0$, and $g^{(p-1)/2}\bmod p\ne1$, and $g^{(p-1)/p_1}\bmod p\ne1$, and $g^{(p-1)/p_2}\bmod p\ne1$, and $g^{(p-1)/p_3}\bmod p\ne1$. In the affirmative, and only then, $g$ is a generator of $\mathbb Z_p^*$.

Additions:

• Computing $g^k\bmod p$ is feasible with a modest computer, and common, for integers of many thousands of bits: $2\log_2(k)$ modular multiplications are enough to compute $g^k\bmod p$; see modular exponentiation.
• If the list $L$ was not a given, we could try $g$ at random (or small primes by increasing orders, which is slightly more efficient than trying small integers by increasing order). If all the primes dividing $(p-1)/2$ are large (which is the case here), nearly 50% of candidates will work, thus a search won't be too long.
• Often, we want a generator of a subgroup of order one of the large primes dividing $p-1$, say $p_3$; we can get that as $g'=g^{(p-1)/p_3}\bmod p$.

Answer 2

Even for the simple case of primitive roots, there is no know general algorithm for finding a generator except trying all candidates (from the list).

If the prime factorization of the Carmichael function $\lambda(n)\;$ or the Euler totient $\varphi(n)\;$ is known, there are effective algorithms for computing the order of a group element, see e.g. Algorithm 1.4.3 in H. Cohen's book A Course in Computational Algebraic Number Theory. A better available source maybe Algorithm 4.79: Determining the order of a group element from Applied Cryptography by A.J. Menezes et al. (you can download a pdf of ch. 4 from http://cacr.uwaterloo.ca/hac/).

In your case for prime $ p = 2p_{1}p_{2}p_{3} + 1$ you have the easy complete factorization $$\varphi(p)=p-1=2p_{1}p_{2}p_{3}$$

Answer 3

fgrieu's answer in algorithmic shape:

Given is prime $p$ and multiplicative group $(\Bbb Z_p^*, \cdot)$.

1.) Find all prime factors $\{p_1,p_2,...,p_k\}$ of $p-1$.

2.) Iterate through $g = 2,3,... $ until a generator is found,

where $g$ is a generator of $(\Bbb Z_p^*, \cdot)$, iff

\begin{equation}\forall i\in\{1,...,k\}: g^\frac{p-1}{p_i}\neq 1 \mod p \end{equation}

Step 2.) terminates due to existence of the generator.