Cryptography Reference
In-Depth Information
end do;
g
end proc:
Example 2.18
We use
findgenerator
to compute a primitive root modulo a
1024-bit prime. Let
> q1 := 56137884923782343720963962669353842133023988148634449590683884541746322145\
87113127165567687732559098437668155861260540297330848898848261719781963459449179:
q2 := 53676479018722918347121521968614239171438539295666062730702284235254895063\
28707875866844215864177767975538660113907335828570679570907425483448984476864331:
q1
and
q2
are (most likely) primes as can be seen by applying Maple's function
isprime
which will be discussed later; if this function returns
true
then the
tested number is, with high probability, prime. Also, we check by means of the
binary logarithm that both numbers have 511 bits:
> isprime
∼
([q1, q2]);
ilog2
∼
([q1, q2]);
[true, true]
[510, 510]
Now, we set
p := 4*q1*q2+1
and we check that this number—which we do
not print—is a 1024-bit prime:
> p := 4*q1*q2+1:
isprime(p);
ilog2(p);
true
1023
Next we compute a primitive root modulo
p
, i.e., a generator of the cyclic group
Z
p
:
> findgenerator(p, [[2, 2], [q1, 1], [q2, 1]])
5071585817830158387456607689247125562633578183352365708882841202137180590754717042\
56887456925344543886456402017227468479254316677005127839147120046714053127092723\
78225388310351970876146651714842638782711686064194343918066971518084609972932972\
016473496364377155064475020181439668410998543691194181991739840272
Z
p
was easily found because we knew the factorization
Note that a generator of
q
2 but we would not be able to find such a generator given only
p
.
Indeed, Maple has a function,
numtheory:-primroot
, that computes the first
primitive root modulo an integer
n
p
−
1
=
4
·
q
1
·
Z
n
is cyclic but this function is
unable to compute a primitive root modulo the prime
p
above within reasonable
time. The reason is that Maple does not know the factorization of
p
>
1 such that
−
1 and so it
−
tries to obtain it but the prime factors of
p
1 are too large.
Exercise 2.25
Write a Maple program that computes a prime
p
and the factorization
of
p
−
1, given the sizes of the prime factors of
(
p
−
1
)/
2, by pseudo-randomly
choosing these factors.
Z
n
is cyclic and then, as
already mentioned, a
primitive root
modulo
n
is a generator of
Even if
n
is not prime, it may be the case that the group
Z
n
, i.e., an element