Cryptography Reference
In-Depth Information
1. “
p
is composite” (i.e., not a prime), which is always a true statement, or
2. “
p
is prime”, which is only true with a high probability.
If the algorithm output is “composite”, the situation is clear: The integer in question
is not a prime and can be discarded. If the output statement is “prime”,
p
is probably
a prime. In rare cases, however, an integers prompts a “prime” statement but it
lies
,
i.e., it yields an incorrect positive answer. There is way to deal with this behavior.
Practical primality tests are
probabilistic algorithms
. That means they have a second
parameter
a
as input which can be chosen at random. If a composite number
p
together with a parameter
a
yields the incorrect statement “
p
is prime”, we repeat
the test a second time with a different value for
a
. The general strategy is to test a
prime candidate
p
so often with several different random values
a
that the likelihood
that the pair (
p
,
a
) lies every single time is sufficiently small, say, less than 2
−
80
.
Remember that as soon as the statement “
p
is composite” occurs, we know for
certain that
p
is not a prime and we can discard it.
Fermat Primality Test
One primality test is based on Fermat's Little Theorem, Theorem (6.3.2).
Fermat Primality Test
Input
: prime candidate
p
and security parameter
s
Output
: statement “
p
is composite” or “
p
is likely prime”
Algorithm
:
1
R
i
= 1TO
s
∈{
2
,
3
,...,
p
−
}
1.1
choose random
a
2
IF
a
p
−
1
1.2
≡
1
1.3
RETURN (“
p
is composite”)
2
RETURN (“
p
is likely prime”)
The idea behind the test is that Fermat's theorem holds for all primes. Hence,
if a number is found for which
a
p
−
1
1 in Step 1.2, it is certainly not a prime.
However, the reverse is not true. There could be composite numbers which in fact
fulfill the condition
a
p
−
1
≡
≡
1. In order to detect them, the algorithm is run
s
times
with different values of
a
.
Unfortunately, there are certain composite integers which behave like primes in
the Fermat test for many values of
a
. These are the
Carmichael numbers
.Givena
Carmichael number
C
, the following expression holds for all integers
a
for which
gcd(
a
,
C
)=1:
a
C
−
1
≡
1mod
C
Such special composites are very rare. For instance, there exist approximately only
100
,
000 Carmichael numbers below 10
15
.
