Cryptography Reference
In-Depth Information
Z
1009
, i.e., an element of
Z
1009
of order 1008. By Proposition 2.6 we have that, since the quotients of 1008
by its three prime factors are 504, 336 and 144, we need to find an element
g
in the
group such that
g
504
Using this information we try to find a generator of
1,
g
336
1 and
g
144
=
=
=
1. We start by trying the element
∈ Z
1009
:
> 2&ˆ504 mod 1009;
2
1
This already tells us that 2 is not a primitive root modulo 1009. The same happens
with the successive values 3, 5, …(some values such as 4 need not be tested because
once we know that 2 is not a generator we also know that 4
2
2
is not a generator
=
either) until 11 for which we find:
> 11&ˆ504 mod 1009;
1008
> 11&ˆ336 mod 1009;
374
> 11&ˆ144 mod 1009;
935
Thus we see that 11 satisfies the conditions of Proposition 2.6 and hence is a
primitive root modulo 1009.
The preceding example suggests the following algorithm to find a generator of
Z
p
assuming that the prime factors of
p
−
1 are known:
∈ Z
p
at random and check whether it satisfies
x
(
p
−
1
)/
q
•
Choose an element
x
=
1
for each prime factor
q
of
p
−
1.
•
If for some prime factor
q
this does not hold, discard
x
and choose a new random
element, repeating the process until a generator is found.
This method gives a probabilistic algorithm which runs in expected polynomial
time on len
(
p
)
. The algorithm performs a sequence of Bernoulli trials (choosing
Z
p
at random) with success probability
φ(
−
)/(
−
)
elements of
p
1
p
1
(since, by
φ(
−
)
−
Theorem2.16, there are
1 elements in the group) and the
expected value of the random variable that estimates the number of trials for the first
success is
p
1
generators out of
p
by Proposition 2.2. Since checking whether a candidate
element is a primitive root requires one modular exponentiation for each prime factor
of
p
(
p
−
1
)/φ(
p
−
1
)
−
1 and the number of these prime factors is clearly
O
(
len
(
p
))
, we see that each
trial requires polynomial time on len
and hence to show that the generator-finding
algorithm runs in expected polynomial time it suffices to see that the expected number
of trials is also polynomial in len
(
p
)
. This follows from a theorem from analytic
number theory due to Rosser and Schoenfeld (see, e.g., [7, Theorem 8.8.7] or also
[60, Exercise 4.1]) which shows that, for
n
(
p
)
e
γ
(
≥
3,
n
/φ(
n
)<
ln ln
n
)
+
3
/(
ln ln
n
)
,
where
γ
is Euler's constant (cf. [7, p. 26]). Thus the expected number of trials is
(
p
−
1
)/φ(
p
−
1
)
=
O
(
ln ln
p
)
.
