Cryptography Reference
In-Depth Information
2.15.2 Computing the order of a group element
We can now return to the original problem of computing the order of an element in a finite
field.
=
i
=
1
l
e
i
i
is known.
Then one can determine the order of g in O
(log(
q
) log log(
q
))
multiplications in
∈ F
q
and assume that the factorisationq
−
Theorem 2.15.10
Let g
1
F
q
.
g
(
q
−
1)
/l
e
i
. Since
m
Proof
The idea is to use Algorithm
4
to compute all
h
i
=
=
O
(log(
q
))
F
q
. One can then compute all
h
l
this requires
O
(log(
q
)loglog(
q
)) multiplications in
for
f<e
i
and, since
i
=
1
l
e
i
i
1
≤
=
q
−
1 this requires a further
O
(log(
q
)) multiplications.
i
The complexity in Theorem
2.15.10
cannot be improved to
O
(log(
q
) log log(
q
)
/
log(log(log(
q
)))) using the result of equation (
2.6
) because the value
m
is not always
(log(
q
)).
2.15.3 Computing primitive roots
F
q
is a cyclic group and that a primitive root in
F
q
is an element of order
q
Recall that
−
1.
−
We assume in this section that the factorisation of
q
1 is known.
One algorithm to generate primitive roots is to choose
g
∈ F
q
uniformly at random and
to compute the order of
g
using the method of Theorem
2.15.10
until an element of order
q
∈ F
q
is a primitive root is
ϕ
(
q
1).
Using Theorem
A.3.1
, this probability is at least 1
/
(6 log(log(
q
))). Hence, this gives an
algorithm that requires
O
(log(
q
)(log(log(
q
)))
2
) field multiplications in
−
1 is found. The probability that a random
g
−
1)
/
(
q
−
F
q
.
We now present a better algorithm for this problem, which works by considering the
prime powers dividing
q
−
1 individually. See Exercise 11.2 of Section 11.1 of [
497
]for
further details.
Theorem 2.15.11
Algorithm
5
outputs a primitive root. The complexity of the algorithm is
O
(log(
q
) log log(
q
))
multiplications in
F
q
.
Proof
The values
g
i
are elements of order dividing
l
e
i
.If
g
l
e
i
−
1
1 then
g
i
has order exactly
l
e
i
. On completion of the while loop the value
t
is the product of
m
elements of maximal
coprime orders
l
e
i
. Hence,
t
is a primitive root.
Each iteration of the while loop requires
O
(log(
q
)loglog(
q
)) multiplications in
=
i
i
F
q
.It
remains to bound the number of iterations of the loop. First, note that, by the Chinese
remainder theorem, the
g
i
are independent and uniformly at random in subgroups of order
l
e
i
. Hence, the probability that
g
l
e
i
−
1
1
/
2 and the expected number of trials
for any given value
g
i
less than or equal to 2. Hence, the expected number of iterations of
the while loop is less than or equal to 2. This completes the proof.
=
1is1
/l
i
≤
i
i
