Cryptography Reference
In-Depth Information
Input
:
n
Output
: a nontrivial factor of
n
Complexity
:
(
B
) arithmetic operations
1:
pick
x
at random in
O
{
2
,...,
n
−
1
}
2:
if
gcd(
x
1
then
3:
output this gcd and stop
4:
end if
5:
i
,
n
)
=
1
6:
while
gcd(
x
←
−
1
,
n
)
=
1
do
x
i
x
←
mod
n
7:
i
←
i
+
1
8:
9:
end while
10:
if
x
=
1
then
11:
fail
12:
else
13:
−
,
output gcd(
x
1
n
) and stop
14:
end if
Figure 7.7.
Pollard
p
−
1 Factorization Algorithm.
p
−
1 are small. We call it the
p
−
1 method (see Ref. [148]). When all prime factors
of
p
−
1 are smaller than
B
, we say that
p
−
1is
B
-
smooth
.
Concretely, we assume that there exists some threshold
B
such that there exist two
prime factors
p
and
q
of
n
such that
p
−
1is
B
-smooth and
q
−
1isnot
B
-smooth.
O
(
4
√
n
) works.) Fig. 7.7 shows the
Pollard p
(In most examples,
B
=
−
1
algorithm
.
It simply consists of computing
x
B
!
mod
n
. The modulo
p
part of this number will
1 is a factor of
B
!, and therefore (
x
B
!
be congruent to 1 since
p
−
mod
n
)
−
1 has a
common factor
p
with
n
which can be found by a gcd computation.
Conversely, if
n
contains a
B
-smooth factor
p
, then for some “
B
-small”
t
the
t
! integer is a multiple of
p
1, hence
x
t
!
−
≡
1 (mod
p
), which can be detected by
computing the gcd of (
x
t
!
mod
n
)
−
1 and
n
as in the rho method. More precisely, if
p
α
1
1
p
α
r
r
p
−
1
=
···
is the prime factorization of
p
−
1, we take
α
i
p
i
=
max
j
α
j
p
j
.
For
t
≥
α
i
p
i
, we know that for all
j
we have at least
α
j
multiples of
p
j
which are
lesser than
t
,so
p
α
j
j
divides
t
! for all
j
,so
p
−
1 divides
t
!. We notice that
α
i
p
i
lies
between
B
and
B
log
2
p
since
α
i
<
log
2
p
. In typical cases,
α
j
's corresponding to large
α
i
p
i
is actually the largest prime factor of
p
−
1 which is
approximated by
B
.So
t
only needs to be slightly larger than
B
to ensure the property.
This is what we meant by “
B
-small.”
p
j
's are all equal to 1, so
It is a bit more tricky to know when the equality modulo
p
does not imply a full
equality modulo
n
in order to make the algorithm succeed. This is quite easy when
n
has a prime factor
p
such that
p
−
1is
B
-smooth
and
a prime factor
q
such that
q
1
is a factor of
t
!, but
r
is not, so unless the multiplicative order of the original
x
is zero
−
1 contains a large prime factor
r
: when
t
becomes slightly greater than
B
,
p
−
Search WWH ::
Custom Search