Cryptography Reference
In-Depth Information
P
=
NP
P
=
NP
is also sufficient for the factoriza-
tion problem to be difficult but this does not seem to be the case. There is a subclass
of problems within
. One might wonder whether
NP
, called
NP
-complete problems, which have the property
that all other problems in
NP
can be reduced to any one of them in polynomial time
and hence proving that an
NP
-complete problem is in
P
is enough to show that
P
=
NP
and there are a
great number of them (for example, the
Traveling Salesperson problem
is one) but
the factorization decision problem is not believed to be among them. See [6] for a
more detailed discussion of these questions.
.
NP
-complete problems are the hardest problems in
NP
2.3.3 Running Times of Some Simple Algorithms
We are going to obtain estimates of the running time of a couple of very ancient
algorithms and we will perform an experiment using Maple to check how close
these estimates are to the actual running time of a specific implementation. As we
will see, prime numbers play a crucial role in cryptography and hence it is very
important to have efficient algorithms that allow us to distinguish between primes
and composites. This is the task of a
primality test
, an algorithm that takes as input a
positive integer and outputs
true
in case the integer is prime and
false
otherwise.
The distribution of prime numbers and efficient primality tests are studied in Chap.
6
but here, as a preliminary example, we are going to study a couple of primality tests
which, although inefficient, are important because they play an auxiliary role in many
other algorithms: the
sieve of Eratosthenes
and
trial division
.
2.3.3.1 The Sieve of Eratosthenes
One of the oldest algorithms that can be used for primality testing is the sieve of
Eratosthenes, which was known more than 2200 years ago and is still today the most
efficient method to generate all the primes less than a given integer. The sieve takes
as input a positive integer
n
n
as follows.
Start with the list of all the integers between 2 and
n
. The first number in the list is 2,
which is prime, and we start by crossing off all proper multiples of 2. We repeat this
process by picking, at each stage, the next number
i
in the list that is not crossed off
(note that
i
is then necessarily a prime) and crossing off all proper multiples of
i
.
This process is repeated while
i
≥
2 and builds the list of all the primes
≤
≤
√
n
, at which point the numbers that remain
without having been sieved out are the primes
n
.
Next we give aMaple implementation of the sieve. To economize on memory only
odd integers (plus the number 2) are considered and, in fact, they are not actually
stored but the array is filled with zeros instead and the crossing off is implemented
by replacing zeros by ones (for which we use the very efficient Maple function
ArrayTools:-Fill
).Moreover, the crossing off ofmultiples of each found prime
number
i
can be started at
i
2
≤
since lower multiples have already been crossed off
