Cryptography Reference
In-Depth Information
decision problem algorithm, its complexity is equal to the complexity of the latter
multiplied by
O
(
(
))
.
The factorization decision problem belongs to the class
len
n
NP
. This is because,
if the answer is 'yes', i.e.,
n
has a nontrivial factor
k
, this can be checked in
polynomial time using a factor
a
as a certificate by just dividing
a
into
n
.This
problem is also in the class co
≤
: if the answer is 'no', then the complete prime
factorization of
n
can act as a certificate that, just by comparing all the prime factors
with
k
, allows a polynomial time verification of the fact that none of them is
NP
k
.
This requires checking that the provided factors are indeed prime (to ensure that
in polynomial time.
The following Maple function may be used to simulate an algorithm for the
factorization decision problem which, when asked whether an integer
n
has a factor
a
such that 2
≤
n
, answers either
true
if this is the case or
false
if there
is no such factor. To do this, we will let Maple compute the complete factorization
first, but we may use Maple's factoring algorithm as an oracle (or a black box to
whose inner workings we do not have access) so that the function answers our
queries without revealing the factors of
n
. The function is the following:
≤
a
≤
k
<
> DecisionFactor := proc(n, k)
evalb(ifactors(n)[2][1][1] <= k)
end proc:
Exercise 2.4
Use the method outlined in the previous example, together with the
function
DecisionFactor
, to factor 247. What is the exact number of calls to
the function in this case?
Exercise 2.5
Write a Maple function that automates the factorization method used
in the previous exercise and, on input a positive integer
n
, outputs the least positive
factor of
n
.
Example 2.4
(
P
versus
NP
)
If a problem is in
P
then it is trivially in
NP
(and also in co
NP
), so that we have
the inclusion
. However, it is not known whether this inclusion is proper
or not and it is generally thought that
P
⊆
NP
P
=
NP
. This open problem, called the
P
problem
, is one of the so-called
Millennium Prize Problems
for the
solution of each of which the
Clay Mathematics Institute
(see [50]) offers a prize
of one million dollars. This problem is highly relevant for cryptography because,
as we shall see later on, both private-key and public-key cryptography rely on the
existence of
one
-
way functions
. That one-way functions exist is only a conjecture
which, as we will see when discussing RSA, would be proved if we could show,
for example, that no polynomial-time factorization algorithm exists. This conjecture
implies that
versus
NP
then public-key cryptogra-
phy as we understand it today would not be possible (and neither would private-key
cryptography).
More specifically, in Chap.
7
we will see that a necessary condition for the secu-
rity of RSA encryption is the hardness of the factorization problem and hence that
P
=
NP
so that, in other words, if
P
=
NP
