Cryptography Reference
In-Depth Information
In order to see that the element
g
returned by this algorithm is indeed a generator
of
G
, we can argue as follows. Consider an element
x
i
∈
G
obtained in the first step
of the algorithm and let
n
i
be the order of
x
i
. By Corollary 2.1,
n
i
divides
n
and,
since
x
n
/
p
i
i
1, we see from Proposition 2.4 that
n
i
is a multiple of
p
e
i
.Nowlet
=
x
n
/
p
e
i
n
i
.As
we have just seen,
n
i
is a multiple of
p
e
i
i
and the cofactor of the latter is removed
when dividing by the gcd, so the order of
y
i
is exactly
p
e
i
y
i
=
i
. By Proposition 2.5 the order of this element is equal to
p
e
i
i
i
gcd
(
n
i
,
n
/
)
. Finally, since the integers
i
p
e
i
i
are pairwise relatively prime, the order of the product
g
of the
y
i
is equal to
i
=
1
p
e
i
=
n
(and hence
g
is a generator of
G
) as a consequence of the following
i
exercise:
Exercise 2.24
Let
(
G
,
·
)
be an abelian group and
x
1
,
x
2
∈
G
elements whose orders
o
1
,
o
2
satisfy gcd
(
o
1
,
o
2
)
=
1. Show that the order of
x
1
x
2
is the product
o
1
o
2
.(Hint:
Prove that the subgroup
G
is the identity subgroup by checking that
its order must divide the orders of
x
1
and
x
2
.If
x
1
=
x
1
∩
x
2
⊆
x
2
=
1 then there is nothing
to prove, otherwise assume that 1
<
d
<
o
1
o
2
is the order of
x
1
x
2
and show that
x
1
,
x
2
∈
x
1
∩
x
2
=
1. Deduce that then
d
divides both
o
1
and
o
2
,givinga
contradiction.)
An implementation of the generator-finding Algorithm 2.5 in Maple, for the case
of the cyclic group
Z
p
, where
p
is prime, is given in the function
findgenerator
below. The first input parameter is for the prime
p
and there is an optional parameter
factors
, which is used for the factors of
p
−
1 in the format
[[
p
1
,
e
1
]
,
[
p
2
,
e
2
]
,...,
[
1 and the
e
i
the corresponding
exponents. The default value is precisely this list which, if not passed to the function,
is computed byMaple by means of the built-in function
ifactors
applied to
p
p
r
,
e
r
]]
where the
p
i
are the prime divisors of
p
−
−
1.
−
1 as input is given because this
will allowMaple to compute a primitive root modulo
p
if this factorization is known,
even in cases when
ifactors
is not able to compute it. The output is a generator
of
The option of providing the factorization of
p
Z
p
.
> findgenerator := proc(p, factors := ifactors(p-1)[2])
local n, l, i, found, e, x, g;
if 'not'(isprime(p)) then
error "%1 is not prime", p
end if;
n := nops(factors);
RandomTools:-MersenneTwister:-SetState();
l:=[];
foritondo
found := false;
e := (p-1)/factors[i][1];
while not found do
x := RandomTools:-MersenneTwister:-GenerateInteger(':-range' = 2 .. p-2);
found := evalb(x&ˆe mod p <> 1)
end do;
e := (p-1)/(factors[i][1])ˆ(factors[i][2]);
l := [op(l), x&ˆe mod p]
end do;
g:=1;
foritondo
g := (g*l[i]) mod p
