Basic Concepts from Probability, Complexity, Algebra and Number Theory - Introduction to Cryptography with Maple - page 90

Remarks 2.3
1. The algorithm just described requires knowledge of the prime factorization of
p 1. If this factorization is not known, then we do not have an efficient algorithm

to find a primitive root modulo p .
2. Note also that the previous algorithm does not make specific use of the fact that
the cyclic group is

−

Z p and works also in expected polynomial time on any cyclic
group of order n where the group operation can be efficiently computed.
3. The previous algorithm is probabilistic but, so far, no deterministic polynomial-
time algorithm is known to find a primitive root modulo p . Such an algorithm
exists if we assume the Extended Riemann Hypothesis (ERH), a widely believed
but unproven conjecture that we describe in Chap. 6 . If the ERH holds then, by
a result of Shoup, the least primitive root modulo p is O ln 6 p

( ) , and hence it

Z p in order until this primitive root is
found. See [60, Research Problem 2.39] for a discussion and references.
4. There is a special case where finding a generator of a group of order n is extremely
easy, namely, when the group order n is prime (which is actually the case for some
groups of cryptographic interest such as elliptic curve groups of prime order).
Then it follows from Corollary 2.1 that any element of G distinct from 1 is a
generator.

suffices to check the least elements of

Exercise 2.23 Write a Maple procedure that computes the smallest primitive root
modulo a prime p

2. Use this procedure to gather some statistical data about
the size of this primitive root and examine these data in relation to a conjec-
ture (mentioned in [60, Research Problem 2.39]) that the least primitive root is
O

>

(( ln p )( ln ln p )) .

There is a variant of the preceding algorithmwhich is given in [180, 11.1], where it
is shown that it runs in expected time O

:= i = 1 q e i .
The algorithm proceeds as before but, instead of looking directly for a generator of
Z p , it proceeds to find elements (which are chosen at random) of order q e i

4

(( len ( p )) ) . Suppose that p − 1

for each

i

Z p .
This algorithm works, more generally, for any finite cyclic group, and may be
summarized as follows:

i = 1 ,..., r . Once these r elements are found, their product is a generator of

Algorithm 2.5. Computation of a generator of a finite cyclic group .

= i = 1 p e i
i

Input : A finite cyclic group G of order n and the prime factorization n .

Output : A generator g of G .

1. Choose , for each i ∈{ 1 ,..., r } , elements in G at random until finding x i ∈ G such

that x n / p i
i

1.
2. Set , for each i

=

x n / p e i ∈{ 1 ,..., r } , y i :=

i

.

:= i = 1 y i .

i

3. return g