Cryptography Reference
In-Depth Information
Example 7.8.
Carmichael Number
n
= 561 = 3
·
11
·
17 is a Carmichael number since
a
560
≡
1 mod 561
for all gcd(
a
,
561)=1.
If the prime factors of a Carmichael numbers are all large, there are only few bases
a
for which Fermat's test detects that the number is actually composite. For this
reason, in practice the more powerful Miller-Rabin test is often used to generate
RSA primes.
Miller-Rabin Primality Test
In contrast to Fermat's test, the Miller-Rabin test does not have any composite num-
bers for which a large number of base elements
a
yield the statement “prime”. The
test is based on the following theorem:
Theorem 7.6.1
Given the decomposition of an odd prime candi-
date p
1 = 2
u
r
p
−
where r is odd. If we can find an integer a such that
a
r
2
j
a
r
≡
1mod
p
and
≡
p
−
1mod
p
for all j
=
{
0
,
1
,...,
u
−
1
}
, then p is composite. Otherwise, it is
probably a prime.
We can turn this into an efficient primality test.
