Cryptography Reference
In-Depth Information
there are no 2-pseudoprimes among them so that the probability of error in this
interval is zero. Of course, the error probability will be non-null if one chooses much
larger intervals (as it can be shown that the number of 2-pseudoprimes is infinite)
but this suggests that a very fast method to find a large probable prime is to pick at
random an odd integer of the required size and submit it to this test.
The theoretical result that explains the outcomes of these experiments is an old
theorem of Erdös, cf. [60, Theorem 3.4.2], that asserts that if
b
≥
2 the number
of
b
-pseudoprimes that are
≤
x
is
o
(π(
x
))
as
x
→∞
, i.e., pseudoprimes become
increasingly rare compared with primes as
x
grows.
Exercise 6.6
Write a Maple function that, on input
b
and
n
, implements the base-
b
Fermat test for
n
. Use this function to carry out experiments similar to the preceding
ones for different bases
b
such as, for example,
b
=
3or
b
=
5 and also for a given
set of bases such as, for example
{
2
,
3
,
5
,
7
}
.
6.2.1.1 Carmichael Numbers
We have seen that, although the composite number 341 passes the Fermat test to
base 2, it already fails the test to base 3 so the idea arises of considering the Fermat
test for all the possible bases: if an integer
n
passes the test to all the bases, is it
necessarily prime? (note that, as we work modulo
n
it is sufficient to consider the
bases
b
∈ Z
n
such that 1
1).
The answer to the preceding question is no: even considering all the possible bases
we do not get a primality test from Fermat's congruence or, in other words, there
are composite integers
n
that are
b
-pseudoprimes for all the possible bases
b
<
b
<
n
−
∈ Z
n
.
The most straightforward way to see this is to make a search for these integers using
Maple. The following function uses brute force to test whether an odd integer
n
has
this property:
> Ftest := proc(n::odd)
local t, i;
if isprime(n) then
return false
end if;
t:=1;
for i from 2 to n-2 while t=1do
if gcd(i, n) = 1 then
t := Power(i, n-1) mod n
end if
end do;
evalb(t = 1)
end proc:
Now, we search among the odd integers up to 10001 (as we will see in a moment,
the numbers we are looking for are necessarily odd):
> select(Ftest, [seq(2*i+1, i=1..5000)]);
[561, 1105, 1729, 2465, 2821, 6601, 8911]
We have quickly found seven integers less than 10000 that pass all the Fermat
tests while being composite. These numbers have a name:
