Cryptography Reference
In-Depth Information
For a discussion of the subtle problems of conditional probabilities in relation
to the probability of error in the generation of randomly selected prime numbers,
see [BCGP] and [MOV], Section 4.4.
In the following function
prime_l
, the values from Table 10-3 will be
considered. We use the exponentiation function
wmexpm_l()
, which combines
Montgomery reduction with the advantages that accrue from exponentiation of
small bases (see Chapter 6).
Function:
probabilistic primality test à la Miller-Rabin with
division sieve
int prime_l (CLINT n_l
,
unsigned int no_of_smallprimes
,
unsigned int iterations);
Syntax:
n_l
(candidate for primality)
no_of_smallprimes
(number of primes for the division sieve)
iterations
(number of Miller-Rabin test iterations; if
iterations == 0
,
this is determined from Table 10-3)
Input:
Return:
1 if the candidate is “probably” prime
0 if the candidate is composite or equal to 1
int
prime_l (CLINT n_l, unsigned int no_of_smallprimes, unsigned int iterations)
{
CLINT d_l, x_l, q_l;
USHORT i, j, k, p;
int isprime = 1;
if (EQONE_L (n_l))
{
return 0;
}
Now the division test is executed. If a factor is found, then the function is ter-
minated with 0 returned. If 1 is returned by
sieve_l()
, indicating that
n_l
is
itself prime, then the function is terminated with return value 1. Otherwise, the
Miller-Rabin test is carried out.
