Cryptography Reference
In-Depth Information
> select(StrongPseudoPrimeTest[2], [seq(2*i+1, i = 5*10ˆ7 .. 5*(10ˆ7+10ˆ6)-1)]);
[100463443, 100618933, 100943201, 101270251, 101276579, 101649241, 102004421,
102678031, 102690677, 104078857, 104852881, 104857391, 105305443, 105919633,
106485121, 106743073, 106775761, 107543333, 108596953, 109118791, 109437751]
> select(StrongPseudoPrimeTest[2], [seq(2*i+1, i = 5*10ˆ11 .. 5*(10ˆ11+10ˆ6)-1)]);
[1000002977551]
We see that, in contrast with the 21 strong 2-pseudoprimes found in the first
interval, there is only one strong 2-pseudoprime in the second. For comparison,
according to the PNT, the ratio of the expected number of primes in the first interval
to the expected number of primes in the second one is, approximately, the ratio
between the logarithms of 10
12
and of 10
8
, namely, about 1
.
5.
The preceding example again suggests that the number of strong pseudoprimes
drops much faster than the number of primes in relation to the size of the involved
numbers. On top of all this, notice also that the numbers in this experiment are still
very small and this effect will be much stronger on numbers of the size required by
public-key encryption schemes such as RSA, where primes of 1024 or 2048bits are
typically used.
6.2.3 The Miller-Rabin Test
We have noticed that strong pseudoprimes appear to be much scarcer than either
primes or (Fermat) pseudoprimes and this suggests that the strong probable prime
test may be useful for finding large primes. Moreover, the difference with the Fermat
test is not only quantitative but also qualitative: we are going to see that now there
is no analogue of Carmichael numbers and the integers that pass the probable prime
test to all the bases are always prime or, in other words, there are no integers that are
strong pseudoprime relative to all possible bases. For brevity, it is convenient to give
a name to the bases for which a given composite number is a strong pseudoprime:
2
s
t
with
t
odd. The
Definition 6.4
Let
n
be a composite odd integer and
n
−
1
=
Z
n
set of
strong liars
for
n
,
S
(
n
)
, is defined as the set of all elements of
that are not
∈ Z
n
witnesses for
n
or, equivalently, the set of bases in
b
such that
n
is a strong
pseudoprime to the base
b
. Thus
or
b
2
i
t
∈ Z
n
|
b
s
S
(
n
)
={
b
≡
1
(
mod
n
)
≡−
1
(
mod
n
)
for some
i
,
0
≤
i
<
s
}
.
Remark 6.5
Note that strong liars are the bases for which a composite number
behaves in a prime-like fashion as far as the strong probable prime test is concerned.
These bases might deceive us into thinking that a composite is prime, hence their
name. On the other hand, witnesses are just the contrary: they tell us that a number
is composite and never lie.
Example 6.6
The followingMaple procedure computes
S
(
n
)
for
n
an odd composite
integer:
