Cryptography Reference
In-Depth Information
Now we measure the time taken by 200 iterations of the test by the Chinese
method:
> ChineseTimeTest(200);
2.000
Next, after restarting Maple's kernel and recomputing all the parameters, we do
the timing for the ordinary exponentiation:
> TimeTest(200);
6.922
We see that the method that uses the CRT was, for these numbers, almost 3.5
times faster than the ordinary method. A quick check that both methods give the
same result when these parameters are used is the following:
> a := rand(2..n-1)():
evalb(Power(a,e) mod n = chrem([Power(a,e1) mod p,Power(a,e2) mod q],[p,q]));
true
Exercise 2.22 Write a Maple procedure that extends the above method to any pos-
itive modulus whose prime factorization is known. The procedure should compute
the exponentiation modulo each prime power dividing the modulus and then use the
CRT to compute the final result.
Z p
2.7.3 Finding Generators in
The binary exponentiation method, together with Proposition 2.6, gives an efficient
algorithm to test whether a given integer, whose prime factors are known, is the order
of an element of a group. In particular, this can be applied to find a generator of a
cyclic group of order n (given the factorization of n ). One of the more important
classes of cyclic groups is given by the following proposition whose proof will be
given later on, in Corollary 2.6:
Z p
Proposition 2.9
If p is prime then the group
is cyclic of order p
1 .
Z n is cyclic, a generator of this group is also called a primitive
root modulo n (more generally, any integer a such that gcd
When the group
(
a
,
n
) =
1 and a mod n
Z n is also called a primitive root modulo n ). We will now consider
the problem of finding a primitive root modulo a prime.
is a generator of
Example 2.17 Let us consider the following prime:
> nextprime(1000);
1009
If p
=
1009 then p
1 has the following factorization:
> ifactor(1008);
(2)ˆ4 (3)ˆ2 (7)
 
Search WWH ::




Custom Search