Cryptography Reference
In-Depth Information
(ii) Write aMaple procedure that usesWilson's theorem to test primality and perform
an experiment with a sample of numbers of different sizes to check the running
time against the complexity estimated above.
Another natural candidate for a primality test is Fermat's little theorem (Theorem
2.2), according to which if
n
is prime and
b
>
1 is such that gcd
(
b
,
n
)
=
1, then
b
n
−
1
(if
n
satisfies this congruence we also say that
n passes the
Fermat test to base b
). We know that the computation of
b
n
−
1
mod
n
is fast by the
binary method and so it seems that this formula can be used as an efficient primality
test except for a little detail: satisfying this congruence is a necessary condition for
n
to be prime but is not sufficient!
Indeed, look at what happens if we take
b
≡
1
(
mod
n
)
=
2 and
n
=
341:
> Power(2,340) mod 341;
1
31 is composite.
The compositeness of 341 also follows from the fact that if we take
b
Thus 341 satisfies Fermat's congruence with
b
=
2 but 341
=
11
·
=
3 then:
> Power(3, 340) mod 341;
56
Thus 341 passes the Fermat test to base 2 but does not pass it to base 3. This
suggests the following definition:
Definition 6.1
Let
n
be a composite number and
b
>
1 an integer such that
gcd
1. Then
n
is a
pseudoprime
to the base
b
(or a
Fermat pseudoprime
to the base
b
)if
b
n
−
1
(
b
,
n
)
=
≡
1
(
mod
n
)
. For brevity we will simply say that
n
is a
b
-pseudoprime.
The existence of
b
-pseudoprimes seems to make the Fermat test useless as a
primality test but this is really not so if one is satisfied with obtaining a result which
is correct if it says that the number is composite but only probably correct if it says
that the number is prime. In fact, a large odd integer that passes the Fermat test to
base 2 (also known as the Chinese test because Chinese mathematicians discovered
it long before Fermat) is very probably prime. The reason is that the number of
2-pseudoprimes is small in comparison to the number of primes and, moreover, the
ratio of 2-pseudoprimes to primes diminishes sharply as
n
gets large. We are going
to do a few experiments with Maple to get an intuitive feeling about this.
The Fermat test to base 2 is the following:
> Fermat2Test := n -> evalb(Power(2, n-1) mod n = 1):
The function that finds whether a given odd integer is a 2-pseudoprime is the
following:
> Fermat2Pseudoprime := n -> not isprime(n) and Fermat2Test(n):
We can see, for example, that the 2-pseudoprimes less than 10000 are the
following:
