Cryptography Reference
In-Depth Information
Exercise 6.8
Compute the strong pseudoprimes to the base
b
that are less than
3000000 for
b
=
,
,
2
3
5. Compare these sets with the corresponding sets of Fermat
pseudoprimes.
FromExercise 6.8 we see that there are exactly 91 strong pseudoprimes to the base
2 that are less than threemillion. But if we consider additional bases and, in particular,
bases that are relatively prime, then we see that the number of strong pseudoprimes
drops steeply. For example, let us compute the numbers below 3000000 that are
strong pseudoprimes to the bases 2 and 3:
> SPP2and3 := x -> StrongPseudoPrimeTest[2](x) and StrongPseudoPrimeTest[3](x):
> select(SPP2and3, [seq(2*i+1, i=2..15*10ˆ5-1)]);
[1373653, 1530787, 1987021, 2284453]
> map(x -> TestError(x, SPP2and3), [2ˆ22..2ˆ23, 2ˆ24..2ˆ24+2ˆ22, 2ˆ26..2ˆ26+2ˆ22]);
[[2, 268216, 0.000007456621107], [1, 250359, 0.000003994248282], [0, 232342, 0.]]
We see that there are only 4 of these strong pseudoprimes below 3000000 and
also that the probability of error of the test drops sharply as the size of the numbers
increases. Note that there are more efficient algorithms to compute the numbers that
are strong pseudoprimes relative to several bases and some of them were used in
[27] to compute all the integers up to 10
16
that are strong pseudoprime relative to
the bases 2 and 3. There are exactly 52593 such integers and, while this might seem
a considerable number, it is actually small compared to the number of primes less
than 10
16
which is:
> numtheory:-pi(10ˆ16);
279238341033925
This means that a random integer less than 10
16
that passes the strong probable
prime test to bases 2 and 3, has a probability equal to
> evalf(52593/(279238341033925+52593));
1.883444795 10ˆ-10
of being composite, so it is very likely prime. Of course, if one considers more
bases, then this likelihood increases. For example, it is shown in [27] that there is
only one number less than 10
16
that is a strong pseudoprime for all the prime bases
≤
19. Thus a random integer less than 10
16
that passes all these tests will have a
probability greater than 1-10
−
14
of turning out to be prime. In addition to this, the
above experiments suggest that the probability of error also decreases as the size of
the tested number increases or, in other words, that the density of strong pseudoprimes
drops much faster than that of primes as size increases. Although the above samples
are too small to draw this conclusion with confidence, we shall cite below theoretical
results that confirm that this is indeed the case.
Example 6.5
Let us compute the strong 2-pseudoprimes in two intervals of length
10
7
, the first starting at 10
8
and the second starting at 10
12
.
