Cryptography Reference
In-Depth Information
Since
p
does not divide
r
we see that indeed
g
p
t
−
2
(
p
−
1
)
mod
p
t
≡
1
(
)
.Now,to
prove that
g
is a primitive root modulo
p
t
, let us call
n
its order in
Z
p
t
and observe
p
t
p
t
−
1
that, by Corollary 2.1,
n
|
φ(
)
=
(
p
−
1
)
. On the other hand, we have that
g
n
mod
p
t
and hence that
g
n
≡
1
(
)
≡
1
(
mod
p
)
. Since
g
is a primitive root
∈ Z
p
Z
p
modulo
p
(i.e.,
g
mod
p
is a generator), its order in
is equal to
p
−
1 and
p
t
−
1
p
u
divides
n
. Thus
(
p
−
1
)
|
n
|
(
p
−
1
)
and hence
n
=
(
p
−
1
)
with
u
≤
t
−
1. Then,
Z
p
t
, its order must be a proper divisor of
|Z
p
t
|=
p
t
−
1
if
g
is not a generator of
(
p
−
1
)
and hence a divisor of
p
t
−
2
(
p
−
1
)
. Therefore in this case we have that
u
≤
t
−
2
and
g
p
t
−
2
p
t
−
2
−
u
(
p
−
1
)
=
(
g
n
mod
p
t
)
≡
(
)
1
, which is a contradiction and completes
the proof.
Exercise 2.28
(i) Modify the function
findgenerator
in order to make it able to find a
primitive root modulo any integer
n
Z
n
is cyclic. Use the format
proc(n,o:=numtheory:-phi(n), factors:=ifactors(o)[2])
for the input parameter declaration and make sure that the pseudo-randomly cho-
sen elements
x
belong to
≥
2 such that
Z
n
by checking that
igcd
(
x
,
n
)
=
1
. The rest of the
function code should be practically the same as that of
findgenerator
,just
dropping the primality check and replacing
p
−
1
by
o
throughout.
(ii) Use the new function to compute a primitive root modulo 2
q
3
, where
q
is the
prime
q
3944809387454309923. Test the result obtained bymeans ofMaple's
function
numtheory:-primroot
, by checking that if
g
is the primitive root
obtained, then:
>
evalb
(
numtheory
:−
primroot
(
g
−
1
,
2
∗
q
3
=
)
=
g
)
;
gives
true
as output (meaning that
g
is the smallest primitive root greater than
g
1).
(iii) Define a Maple function, based on the previous one, such that the output is the
smallest primitive root modulo
n
which is greater than a given positive integer
t
−
<
n
(if such a primitive root exists). Compare the output of this function with
that of Maple's
numtheory:-primroot
.
2.8 Finite Fields
Finite fields play an important role in cryptography and in this section we show how
to construct them. We start with a small example.
2.8.1 A Field of 4 Elements
We have seen that
Z
n
is a field if and only if
n
is prime. This guarantees, for each
prime
p
, the existence of a finite field of
p
elements (the number of elements of a
