Basic Concepts from Probability, Complexity, Algebra and Number Theory - Introduction to Cryptography with Maple - page 47

precise definition of what a computational problem is. This requires the formulation
of a mathematical model of computation and for this there are several possibilities,
with the computational model of choice being based on Turing machines . Fortunately,
it can be shown that the classification provided by complexity theory is largely inde-
pendent of the computational model used. More precisely, the Church - Turing Thesis
basically says that all computational models are equivalent in the sense that a function
computable in one model is also computable in the other models and the compu-
tational complexities defined by the different models are “polynomially related” so
that polynomial time, and hence efficient computation, can be defined independently
of the adopted model. Thus we do not explicitly choose any one model and we sim-
ply rely on the asymptotic notation previously introduced to give estimates of the
hardness of the problems. We refer the interested reader to [6] for more detailed
complexity theory notions and to [169, 191] for a more specific study of the relation
between complexity and cryptography.
When dealing with computational problems, it is easier to look at decision prob-
lems which are those that admit only a yes/no answer or, in other terms, are solved by
an algorithm that produces as output a unique bit. This might seem too restrictive but,
in practice, it is not so because the computational problems we are interested in can
often be formulated as decision problems in such a way that an efficient algorithm
for the latter gives an efficient algorithm for the former and vice versa.
When classifying computational problems in terms of their relative difficulty it
is useful to include them in complexity classes , some of which we are now going to
define. We will consider only decision problems but other kinds of problems may
also be similarly classified.

Definition 2.14 A decision problem belongs to the class if there exists a deter-

ministic polynomial-time algorithm that solves it. We usually say that these problems
are solvable in polynomial time .

P

There are some decision problems that, while seemingly non-solvable in polyno-
mial time, have the property that a solution can be verified in polynomial time:

Definition 2.15 A decision problem belongs to the class (non-deterministic

polynomial time) if a 'yes' answer can be verified in polynomial time given some
extra information, called a certificate or a witness . Similarly, the decision problem
belongs to the class co

NP

NP

if a 'no' answer can be verified in polynomial time given

a certificate.

Example 2.3 ( The integer factorization problem )
We next give a brief summary of the integer factorization problem because of its
great importance for cryptography; algorithms to solve this problem are studied in
Chap. 6 . This is the computational problem of, given a positive integer n as input,
computing the prime factorization of n . It can be reduced to the factorization search
problem which is the following: Given an integer n > 1, find a nontrivial factor a of

n (i.e, an integer a such that 1 < a < n and there exists an integer b with n = ab )

or determine that no such factor exists (i.e., that n is prime).