Cryptography Reference
In-Depth Information
ln
3
n
(
)
.
We are going to see that this is a viable way to proceed in practice because the
probability that a large composite integer passes the test is actually much lower than
the bound 1
If the number of bases
k
is kept constant, then the test running time is just
O
4
k
. As we saw when discussing the strong probable prime test, the
number of strong pseudoprimes relative to small bases is low in comparison with the
number of primes, and the ratio between these numbers decreases as number size
increases. We are now going to perform a similar experiment with pseudo-random
bases, in order to see that the probability that a composite number passing the test is
much lower than the 4
−
k
bound provided by Theorem 6.9. In order to see this, we will
consider two intervals of length 10
6
, the first starting at 10
7
and the second at 10
15
,
and we will measure the error produced by the Miller-Rabin test with one single base
on these intervals. We will use the previously defined Maple function
TestError
which, in turn, uses
isprime
to distinguish between primes and composites, and we
recall that the latter function is known to give always the correct result for numbers
of this size, so the results of the experiment will be accurate.
/
> randomize();
MillerRabin1 := x -> MillerRabin(x, 1):
TestError(10ˆ7 .. 10ˆ7+10ˆ6, MillerRabin1);
TestError(10ˆ15 .. 10ˆ15+10ˆ6, MillerRabin1);
[7, 61938, 0.0001130034708]
[0, 28845, 0.]
Let us analyze these results. Only seven out of the more than 430000 odd com-
posites in the first interval passed the test and none of the more than 470000 odd
composites in the second interval passed it! If the probability that a composite passes
the test were close to 1
/
4 we would expect over 100000 integers passing the test
in either case. Note that, as the base is pseudo-randomly chosen each time the test
is applied, different results can be obtained when this experiment is repeated, but
the results will not be too far from the ones we have just obtained. This experiment
suggests that the error probability of the Miller-Rabin test is indeed much lower than
4
−
k
and, furthermore, that it decreases sharply as the numbers tested get larger. We
will have a few more words to say about this when we discuss algorithms to generate
random primes of large size.
6.2.4 Other Primality Tests
The Miller-Rabin test is, due to its efficiency, the preferred one for selecting large
(probable) primes for cryptographic use. There are, however, several other tests that
can be used for this purpose and some of them are deterministic and always provide
the correct result. Before mentioning some of these tests, let us go back to Maple's
function
isprime
which we have used in the previous experiment as a “black box”
to provide us with primes or with composites. But what is the algorithm underlying
isprime
? Well, the algorithm is, as of Maple v12, none other than Miller-Rabin's,
combined with some trial division to detect small primes, a variant of the base-2
strong probable prime test and a
Lucas test
. This can be checked by printing Maple's
