Cryptography Reference
In-Depth Information
of
a
. Therefore, all elements of order
d
, being zeros of
x
d
−
1, are powers of
a
.By
Proposition 2.5, a power
a
t
of
a
has order
d
if and only if gcd
(
,
)
=
1 and hence
we have shown that if
a
has order
d
then the elements of order
d
are all the powers
a
t
with gcd
t
d
(
t
,
d
)
=
1. Since there are
φ(
d
)
values of
t
such that 0
<
t
≤
d
and
gcd
(
t
,
d
)
=
1, this means that if there is at least one element of order
d
, then there
are exactly
φ(
d
)
such elements. To complete the proof of the theorem it remains to
∈ F
q
of order
d
must exist. If we denote by
f
show that an
a
(
d
)
the number of
elements of order
d
we know that either
f
(
d
)
=
φ(
d
)
or
f
(
d
)
=
0. But there are
F
q
q
−
1 elements in
and all of them have order equal to some divisor of
q
−
1,
so that
d
|
q
−
1
f
(
d
)
=
q
−
1. On the other hand, by Proposition 2.8 we also have
that
d
|
q
−
1
φ(
d
)
=
q
−
1. Thus
f
(
d
)
is always equal to
φ(
d
)
and never 0, which
completes the proof.
F
q
of a finite field is cyclic and has
Corollary 2.5
The multiplicative group
φ(
q
−
1
)
generators.
We can now see that, for every prime
p
, there are primitive roots modulo
p
:
Z
p
is a cyclic group of order p
Corollary 2.6
If p is a prime number, then
−
1
which
has
φ(
p
−
1
)
generators.
Exercise 2.38
Show that if
p
is a prime number, then the only square roots of 1
modulo
p
are 1 and
−
1.
Z
p
(for
p
prime)
and its Maple implementation. That algorithm works in any finite cyclic group and
the corresponding Maple function can easily be adapted to find a generator of the
multiplicative group of a finite field. However, it is not necessary to do this because
Maple already has this function implemented in the package
GF
. Using as example
our previously defined 256-element field
F256
, the Maple functions to test whether
a given field element is a generator and to pseudo-randomly choose a generator
are
F256:-isPrimitiveElement
and
F256:-PrimitiveElement()
,
respectively.
We have seen in Sect.
2.7
an algorithm to compute a generator of
Example 2.27
Suppose we want to check whether the element corresponding to the
polynomial
x
is a generator. We compute:
> F256:-isPrimitiveElement(F256:-ConvertIn(x));
false
Thus this element is not a generator. Let's now check the element corresponding
to
x
+
1:
> a := F256:-ConvertIn(x+1);
a:=(x + 1) mod 2
> F256:-isPrimitiveElement(a);
true
