Cryptography Reference
In-Depth Information
∈ Z
n
Definition 6.2
A composite integer
n
that is
b
-pseudoprime for all
b
is called
a
Carmichael number
.
Carmichael numbers are an obstacle that prevents use of the Fermat test to prove
that a prime number is indeed prime. As we have seen, 561 is the smallest Carmichael
number but there are many others (in fact, their number is infinite, see reference
below). Carmichael numbers are easily characterized by the following theorem. This
result is called
Korselt's criterion
and, amazingly, it was discovered before any
Carmichael number was known; it seems that Korselt believed that such numbers
did not exist but, in 1910, R.D. Carmichael discovered 15 of them. Recall that an
integer is called square-free if it is not divisible by the square of any prime (or, for
that matter, by the square of any integer).
Theorem 6.5
(Korselt's criterion)
A composite integer n
>
2
is a Carmichael number
if and only if it is square-free and
for each prime divisor p of n.
Moreover, the number of distinct prime factors of a Carmichael number is at least
3
.
(
p
−
1
)
|
(
n
−
1
)
Proof
Assuming that
n
is a Carmichael number, we first show that
n
is square-free.
Suppose, on the contrary, that
p
is a prime such that
p
2
n
.Let
g
be a primitive root
modulo
p
2
, which exists by Exercise 2.27. The order of
g
in
|
Z
p
2
is equal to the order
p
2
of this group which is
φ(
)
=
p
(
p
−
1
)
.If
n
has no prime divisors other than
p
,
g
mod
p
2
and, otherwise, let
n
be the product of all the prime divisors of
n
other than
p
, and let
b
a solution (which exists by the Chinese remainder theorem)
of the system of congruences
let
b
=
mod
p
2
x
≡
g
(
)
(6.1)
mod
n
)
x
≡
1
(
Then
b
is a primitive root modulo
p
2
(since
b
mod
p
2
≡
g
(
)
) and, moreover, satisfies
gcd
1 because it is not divisible by
p
nor by any other prime divisor of
n
in
case they exist (since
b
(
b
,
n
)
=
mod
n
)
≡
1
(
). We show that
n
is not
b
-pseudoprime. Indeed,
if
b
n
−
1
then, since
p
2
n
,wealsohavethat
b
n
−
1
mod
p
2
≡
1
(
mod
n
)
|
≡
1
(
)
.Inthis
Z
p
2
, which is equal to
p
case, the order of
b
in
(
p
−
1
)
, divides
n
−
1 by Proposition
2.4. But
p
|
n
implies
n
−
1
≡−
1
(
mod
p
)
and hence
n
−
1 cannot be divisible
by
p
(
p
−
1
)
, a contradiction. Thus we have shown that any Carmichael number is
square-free.
We next prove that, for each prime
p
dividing
n
,
.Let
g
beaprimitive
root modulo
p
. Since
n
is square-free, using the Chinese remainder theorem we can
find an integer
b
such that
b
(
p
−
1
)
|
(
n
−
1
)
≡
g
(
mod
p
)
and
b
≡
1
(
mod
n
/
p
)
. Then gcd
(
b
,
n
)
=
1
and
b
n
−
1
g
n
−
1
≡
(
mod
p
)
. On the other hand, since
n
is a Carmichael number we
have that
b
n
−
1
and hence
g
n
−
1
≡
1
(
mod
p
)
≡
1
(
mod
p
)
too. Since
g
has order
Z
p
, it follows from Proposition 2.4 that
p
−
1in
(
p
−
1
)
|
(
n
−
1
)
.
For the converse, suppose that
n
is square-free and
p
−
1 divides
n
−
1 for all
(
,
)
=
prime divisors of
n
.Let
b
be an integer such that gcd
b
n
1. Then, for every
prime divisor
p
of
n
we have that
b
p
−
1
≡
(
)
(
−
)
|
(
−
)
1
mod
p
and, since
p
1
n
1
,
