Cryptography Reference
In-Depth Information
and
3474749660383 = 1303
·
16927
·
157543
.
These two numbers are the only pseudoprimes below
10
13
to the prime bases
2, 3, 5, 7, and 11 (see [Rose], Section 3.4).
Fortunately, the number of bases of strong pseudoprimes is again diminished
by these numbers themselves. M. Rabin has proved that for a composite number
n
there are fewer than
n/
4
bases
a
,
2
≤ a ≤ n −
1
, to which
n
is a strong
pseudoprime (see [Knut], Section 4.5.4, Exercise 22, and [Kobl], Chapter 5).
From this we obtain with
k
-fold repetition of the test with
k
randomly chosen
bases
a
1
,...,a
k
a probability smaller than
4
−
k
that a strong pseudoprime has
been falsely accepted as a prime. Therefore, for the same amount of work, the
Miller-Rabin test is superior to the Solovay-Strassen test, which with
k
repetitions
has probability of error bounded by
2
−
k
.
In practice, the Miller-Rabin test does much better than advertised, since the
actual probability of error is in most cases much smaller than that guaranteed by
the theorem of Rabin (see [MOV], Section 4.4, and [Schn], Section 11.5).
Before we get down to implementing the Miller-Rabin test, we look at two
approaches to improving efficiency.
By beginning the Miller-Rabin test with a division sieve that divides the prime
candidates by small primes, we obtain an advantage: If a factor is found in the
process, then the candidate can be eliminated from consideration without the
expense of a Miller-Rabin test. The question at once presents itself as to how
many prime numbers would be optimal to divide by before undertaking the MR
test. We give a recommendation due to A. K. Lenstra: The greatest efficiency is
achieved if one divides by the
303
prime numbers less than
2000
(see [Schn],
Section 11.5). The reason for this arises from the observation that the relative
frequency of odd numbers without prime divisors less than the bound
n
is about
1
.
12
/
ln
n
. Dividing by prime numbers under
2000
eliminates about
85
percent
of all composite numbers without using the MR test, which is then used only on
the remaining candidates.
Each division by a small divisor requires computation time of order only
O
(ln
n
)
. We make use of an efficient division routine especially for small divisors
and use it in instituting the division sieve.
The division sieve is implemented in the following function
sieve_l()
. It, in turn, uses the primes less than
65536
stored in the field
smallprimes[NOOFSMALLPRIMES]
. The primes are stored as differences, where for
each prime only a byte of storage is required. The diminished access to these
primes is not a serious problem, since we are using them in their natural order.
The case that the candidate itself is a small prime and is contained in the prime
number table must be specially indicated.
Finally, we profit from the exponentiation function for small bases (see
Chapter 6) by applying the MR test with small primes
2
,
3
,
5
,
7
,
11
,... < B
