Cryptography Reference
In-Depth Information
in the early 1990s that it was proven that there are infinitely many Carmichael
numbers (see [Bund], Section 2.3).
The relative frequency of numbers less than
n
that are relatively prime to
n
is
φ
(
n
)
n −
1
1
−
(10.24)
(for the Euler
φ
function see page 177), so that the proportion of numbers that
are not relatively prime to
n
is close to
0
for large
n
. Therefore, in most cases
one must run through the Fermat test very often to determine that a Carmichael
number is composite. Letting
a
run through the range
2
≤ a ≤ n −
1
, eventually,
one encounters the smallest prime divisor of
n
, and it is only when
a
assumes this
value that
n
is exposed as composite.
In addition to the Carmichael numbers there are further odd composite
numbers
n
for which there exist natural numbers
a
with
gcd(
a, n
)=1
and
a
n
−
1
≡
1mod
n
. Such numbers are known as
pseudoprimes to the base
a
.To
be sure, one can make the observation that there are only a few pseudoprimes
to the bases 2 and 3, or that, for example, up to
25
×
10
9
there are only
1770
integers that are simultaneously pseudoprimes to the bases 2, 3, 5, and 7 (see
[Rose], Section 3.4), yet the sad fact remains that there is no general estimate of
the number of solutions of the Fermat congruence for composite numbers. Thus
the problem with the Fermat test is that the uncertainty as to whether the method
of random tests will reveal a composite number as such cannot be correlated with
the number of tests.
However, such a connection is offered on the basis of the Euler criterion (see
Section 10.4.1): For an odd prime
p
and for all integers
a
that are not multiples of
p
,wehave
a
p
mod
p,
a
(
p
−
1)
/
2
≡
(10.25)
where
p
≡±
1mod
p
denotes the Legendre-Jacobi symbol. In analogy
to Fermat's little theorem we obtain an exclusionary criterion by taking the
contrapositive of the following statement:
If for a natural number
n
there exists an integer
a
with
gcd(
a, n
)=1
and
a
(
n
−
1)
/
2
≡
n
mod
n
,then
n
cannot be a prime number.
The required computational expenditure for establishing this criterion is the
same as that for the Fermat test, namely
O
log
3
n
.
As with the Fermat test, where there is the problem of pseudoprimes, there
exist integers
n
that for certain
a
satisfy the Euler criterion although they are
composite. Such
n
are called
Euler pseudoprimes
to the base
a
. An example is
