Cryptography Reference
In-Depth Information
RP
Definition 2.16
A decision problem belongs to the class
(
randomized polyno-
mial time
) if there exists a no-biased Monte Carlo algorithm to solve the problem.
Similarly, the problem is in co
RP
if there exists a yes-biased Monte Carlo algo-
rithm that solves it. The intersection
RP
∩
co
RP
defines the class
ZPP
(
zero
-
error
probabilistic polynomial time
).
actually consists of the decision
problems which can be solved by a Las Vegas algorithm.
It is not difficult to see [6, 191] that the class
ZPP
Example 2.5
Let us consider the decision problem that asks, given a positive odd
integer
n
, whether
n
is composite. As we will see, by Theorem 6.7 the Miller-Rabin
test is a no-biased Monte Carlo algorithm for this problem and hence the decision
compositeness problem is in
. By the same reason the decision primality problem
(given a positive integer
n
,is
n
prime?) belongs to
co
RP
RP
. In fact, since the 1990s it
has been known that this problem also belongs to
but, from
a theoretical point of view, all these results have been superseded by the proof in
2002 [3] that the decision primality problem is in
RP
and hence to
ZPP
P
(taking into account that, clearly,
P
⊆
ZPP
⊆
RP
).
are defined by probabilistic polynomial-time algo-
rithms which make only one-sided errors. We can consider also algorithms that can
make two-sided errors, i.e., what we referred earlier to as Atlantic City algorithms.
This idea leads to the definition of the class
The classes
RP
and co
RP
BPP
:
Definition 2.17
A decision problem belongs to the class
BPP
(
bounded
-
error
probabilistic polynomial time
) if there exists a constant
0 and a probabilis-
tic polynomial-time algorithm that produces a 'yes' or 'no' answer which is correct
with probability
ε>
>
1
/
2
+
ε
.
We remark that if a probabilistic algorithm gives a correct answer with probabil-
ity greater than a constant
>
/
1
2, then one may obtain from it an algorithm that,
for any
.In
the case of a Monte Carlo algorithm it suffices to take
k
independent iterations of
the original algorithm, where
k
satisfies 2
−
k
ε>
0 produces a correct answer with probability greater than 1
−
ε
. In the case of an Atlantic City
algorithm, one considers a sufficient number of iterations of the algorithm and then
takes the “majority answer” (see, e.g., [191, Proposition 4.14]). This last remark has
the consequence that, although the inclusion
<ε
RP
⊆
BPP
is probably proper (and
it is suspected that
BPP
may be much larger than
RP
), the problems in
BPP
are
considered tractable.
Example 2.6
Consider the following problem: Given a positive integer
k
,findaprime
of (at least)
k
bits in time polynomial in
k
. We will see that many cryptographic
algorithms use large primes so the problem has a definite cryptographic interest.
However, no (deterministic) polynomial-time algorithm is known so far to solve
this problem! (see [157] for a discussion and references). Despite this apparently
unfortunate situation, there is no problem to find large primes for cryptographic use,
which can be done efficiently by using probabilistic algorithms. The idea is simply to
