Cryptography Reference
In-Depth Information
We pick a random
-bit
n
until it passes a primality test with
k
iterations. The
probability that we do not find a prime number after
c
trials is
1
)
c
, which is
(
1
−
arbitrarily small with
c
). The probability
p
w
that this algorithm lets a composite
number pass after
c
trials is lesser than
c
4
−
k
. Therefore we can pick
k
=
(
=
(log
). We
3
) because
k
is negligible with
respect to
c
and most composite numbers are ruled out by the very first iteration.
notice that the
k
factor vanishes in the complexity
O
(
c
This algorithm will succeed after
c
=
O
(
) trials, which leads to a complexity of
4
). In practice, we even make sure that the randomly picked
O
-bit number
n
has no
small prime factors by construction (e.g. we do not pick even numbers). Hence, the
running time is indeed smaller in practice.
(
7.2
Factorization
As we saw in Section 7.1, it is easy to recognize prime numbers, and therefore, composite
numbers as well. Given a composite number
n
, it is easy to get a “proof of composite-
ness” (for instance by exhibiting a number
b
such that 0
n
and
b
n
−
1
1).
Here “easy” means within a time polynomial in the size of
n
(namely log
n
). It is how-
ever quite hard to get a nontrivial factor of
n
in general: no polynomial algorithms (in
terms of log
n
) are known for that.
<
b
<
mod
n
=
The first algorithm we think of is based on the
trial
di
vision algorithm
depicted in
Fig. 7.1: we try to divide
n
by all integers
i
from 2 to
√
n
until a factor is found. This
algorithm will pull a factor out of
n
within a complexity of
O
(
p
) arithmetic operations
where
p
is the smallest prime factor of
n
.
3
In this section we list a few exponential algorithms which have a better complexity.
7.2.1
Pollard Rho Method
Pollard Rho algorithm
(named after t
he
Greek
ρ
character) lowers the complexity of
(
√
p
) where
p
is the smallest prime factor of
n
(see
Ref. [149]). The basic idea is the following.
trial division from
O
(
p
)downto
O
We take a “random” function
f
which can be “factorized” by a mod
p
function
for any factor
p
of
n
: namely such that
f
(
x
)
f
(
x
mod
p
) (mod
p
) for any
factor
p
of
n
. For example we can take any polynomial function. In practice
one always uses
f
(
x
)
≡
x
2
=
+
1 which behaves “like a random function” from a
heuristic viewpoint.
3
Note that we should consider the complexity of arithmetic operations. But the overhead is negligible in
comparison to
p
since it is polynomial in log
n
. We will omit it for simplicity, but recall that the complexity
unit is an “arithmetic operation” and not an elementary binary operation.
Search WWH ::
Custom Search