Cryptography Reference
In-Depth Information
•
One can construct provable primes;
•
One can randomly choose large odd numbers and apply primality (or compos-
iteness) tests.
There are only a few algorithms to construct provable primes (e.g., [7]), and
in practice one randomly chooses large odd numbers and applies primality (or
compositeness) tests. If a number turns out to be composite, then it is discarded and
the next odd number is taken into consideration. The primality decision problem as
captured in Definition 3.27 has attracted many mathematicians in the past.
Definition 3.27 (Primality decision problem)
Given a positive integer
n
∈
N
,
decide whether
n
∈
P
(i.e.,
n
is prime) or not (i.e.,
n
is composite).
There are a couple of algorithms to address the primality decision problem.
Most of them are probabilistic.
17
Only a few deterministic primality testing algo-
rithms are efficient (i.e., run in polynomial time). They are, however, much less
efficient than their probabilistic counterparts. From a theoretical viewpoint, however,
knowing efficient deterministic primality testing algorithms means that the primality
decision problem is in the complexity class
P
(as introduced in Definition 6.6) This
fact was proven in 2002.
18
Numbers that are not truly known to be prime, but which have passed some
probabilistic primality tests, are called
probable primes
or
pseudoprimes
.Some-
times, the term “pseudoprime” is also used to refer to a nonprime (i.e., a composite
number) that has nevertheless passed a probabilistic primality test. For the purpose
of this topic, however, a pseudoprime is a (prime or composite) number
n
that has
passed some specified probabilistic primality tests. Each of these tests makes use of
one or several randomly chosen auxiliary numbers 1
<a<n
.Ifsuchan
a
tells us
that
a
is likely prime (composite), then
a
is a
witness
to the primality (composite-
ness) of
n
. A problem is that a significant fraction of numbers between 2 and
n
1
may be false witnesses (sometimes called
liars
) to the primality of
n
, meaning that
they tell us
n
is prime when it's not. Thus, part of the issue is to be sure that a large
fraction of the numbers
a
in the range 1
<a<n
are true witnesses to either the
primality or the compositeness of
n
. As discussed later, the fatal flaw in the Fermat
test is that there are composite numbers for which there are no witnesses. The other
two probabilistic primality tests have no such flaw.
−
17
The probabilistic primality testing algorithms can be converted into deterministic algorithms if the
Extended Riemann Hypothesis is true. Many mathematicians believe that this hypothesis is true,
and there is no simple evidence to the contrary.
18
http://www.cse.iitk.ac.in/primality.pdf
