Cryptography Reference
In-Depth Information
TABLE 11.1
2
n-1
≡
x(mod n)
n
Is n prime?
2
2
≡
1 (mod 3)
3
Yes
2
3
≡
0 (mod 4)
4
No
2
4
≡
1 (mod 5)
5
Yes
2
5
≡
2 (mod 6)
6
No
2
6
≡
1 (mod 7)
7
Yes
2
7
≡
0 (mod 8)
8
No
2
8
≡
4 (mod 9)
9
No
2
9
≡
2 (mod 10)
10
No
2
10
≡
1 (mod 11)
11
Yes
This isn't a bad idea, actually, if it weren't for the existence of Carmichael numbers;
these are very rare composite integers that fool Fermat's test for any base
b
relatively prime
to
n
. The integer 561 = 3
11
17 is a Carmichael number, and we can prove it in this way:
Take any base
b
relatively prime to 561; so (
b
, 3) = (
b
, 11) = (
b
, 17) = 1. FLT tells us then
2
10
16
that
b
1 (mod 3),
b
1 (mod 11), and
b
1 (mod 17). This tells us then that
560
= (
2
)
280
b
b
1 (mod 3),
560
= (
10
)
56
b
b
1 (mod 11), and
560
= (
16
)
35
b
b
1 (mod 17).
560
Proposition 26 now implies that
b
1 (mod 561) for any base
b
such that (
b
, 561) =
1, and so 561 is a Carmichael number.
Though Carmichael numbers are very rare (much rarer than primes), there are still infi-
nitely many of them. However, we will not prove this. The fact that they exist at all is enough
to avoid using Fermat's test for primality, especially when we can develop better tests which
Carmichael numbers cannot fool. An example of such a test is Miller's test. Miller's test is
based on Fermat's test, but carries it a bit further. In order to prove that it works, we will need
the following, which you should easily be able to prove.
2
PROPOSITION 34
Let
p
be prime, and suppose
x
1 (mod
p
). Then
x
1 (mod
p
)
or
x
).
Proposition 34 says the only square roots of 1 modulo a prime are 1 and
1 (mod
p
1. This fact
will be immensely helpful. Now we can discuss Miller's test, which is based on proposition
34.
Search WWH ::
Custom Search