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
Search WWH ::




Custom Search