Cryptography Reference
In-Depth Information
b
n
−
1
is a power of
b
p
−
1
so that we also have
b
n
−
1
≡
(
)
1
mod
p
. Since each of
these primes
p
divides
b
n
−
1
−
1, their product, namely
n
, also divides it, so that
b
n
−
1
and
n
is
b
-pseudoprime.
Finally, we show that if
n
is a Carmichael number, it is a product of at least
three distinct primes. We only have to show that
n
≡
1
(
mod
n
)
=
pq
, with
p
,
q
,primes,is
impossible. If
n
=
pq
with
p
<
q
, then we know that
n
−
1
≡
0
(
mod
q
−
1
)
.
But
n
−
1
=
p
(
q
−
1
)
+
p
−
1
≡
p
−
1
(
mod
q
−
1
)
, which is not congruent to 0
modulo
q
−
1, completing the proof.
Remark 6.3
Note that a Carmichael number
n
is always odd. Otherwise,
n
−
1 would
−
be odd and hence it could not be divisible by even numbers of the form
p
1 with
p
prime.
Exercise 6.7
Show that
n
is a Carmichael number if and only if
n
is composite and
b
n
for every integer
b
.(Hint:If
n
is a Carmichael number, then for
every prime divisor
p
of
n
,
b
n
≡
b
(
mod
n
)
which, when
p
does not divide
b
, follows
from Fermat's little theorem and the fact that
≡
b
(
mod
p
)
(
p
−
1
)
|
(
n
−
1
).)
Using the preceding theorem we may write a much more efficient test (although
still inefficient because it requires the prime factorization of
n
; factorization algo-
rithms will be discussed later on) to determine whether an odd integer is a Carmichael
number:
> CarmichaelTest := proc(n::odd)
local f, p, c, i;
f := ifactors(n)[2];
p := map(x -> x[1], f);
if nops(p) <= 2 or ormap(x-> evalb(x[2] <> 1), f) then
return false
end if
c:=0;
i:=1;
while c = 0 and i <= nops(p) do
c := (n-1) mod (p[i]-1);
i:=i+1
end do;
evalb(c = 0)
end proc:
With this test we can find, for example, all the Carmichael numbers less than one
million in a matter of seconds:
> select(CarmichaelTest, [seq(2*i+1, i=1..500000)]);
[561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633,
62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601,
278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461,
530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633]
There are 43 Carmichael numbers below one million and their density
decreases quickly as number size grows. We may do an experiment using the func-
tion
TestError
to compare the number of Carmichael numbers with the number
of primes in a given interval. For example, we have:
> map(x ->
TestError(x,CarmichaelTest), [2ˆ20..2ˆ21, 2ˆ24..2ˆ24+2ˆ20, 2ˆ28..2ˆ28+2ˆ20]);
[[10, 73586, 0.0001358769498], [6, 63008, 0.00009521693592], [0, 54150, 0.]]
