Cryptography Reference
In-Depth Information
C.3 Pollard's
p
−
1
Algorithm
∈
N
, and that a smoothness bound
B
has
been selected. Then we execute the following.
(1)
Suppose that we wish to factor
n
∈
N
≤
Choose a base
a
where 2
a<n
and compute
g
= gcd(
a,n
).
If
g>
1, then we have a factor of
n
. Otherwise, go to step (2).
ln(
p
)
and replace
a
by
a
p
m
(mod
n
)
using the repeated squaring method given on page 171. (Note that this
iterative procedure ultimately gives
a
p
≤
B
p
m
modulo
n
for the base
a
chosen in (1).)
B
, compute
m
=
ln(
n
)
(2) For all primes
p
≤
(3)
Compute
g
= gcd(
a
1
,n
). If
g>
1, then we have a factor of
n
, and the
algorithm is successful. Otherwise, the algorithm fails.
−
The reasoning behind Pollard's algorithm is given as follows.
Let
= lcm(
p
a
1
,...,p
a
t
), where
p
a
j
j
runs over all prime powers such that
p
j
≤
ln(
n
)
ln(
p
j
)
.
Since
p
a
j
j
≤
≤
ln(
n
), so
a
j
≤
B
.
n
, then
a
j
ln(
p
j
)
Hence,
.Now,if
p
n
is a prime such that
p
≤
j
=1
p
ln(
n
)
/
ln(
p
j
)
−
1is
B
-smooth,
1)
. Therefore, for any
a
j
a
,
a
then (
p
−
∈
N
with
p
≡
1 (mod
p
), by Fermat's
1
,n
), then
p
g
.If
g
=
n
, then the
little theorem (A.2). Thus, if
g
= gcd(
a
−
algorithm fails. Otherwise, it succeeds.
Example C.2
Let
n
= 13193
, and choose a smoothness bound
B
=13
, then
select
a
=2
. We know that
a
is relatively prime to
n
so we proceed to step
(2).
The table shows the outcome of the calculations for step
(2).
p
2
3
5
7
11
13
m
13
8
5
4
3
3
a
6245
1365
1884
3133
5472
396
Then we go to step
(3)
and check
gcd(
a
−
1
,n
) = gcd(395
,
13193) = 79
.
Thus, we have factored
n
=79
·
167
. Observe that
p
=79
is
B
-smooth since
p
−
1=2
·
3
·
13
, but
q
= 167
is not since
q
−
1=2
·
83
.
The running time for Pollard's
p
−
1 algorithm is
O
(
B
ln(
n
)
/
ln(
B
)) modular
and there exists a prime
p
n
such that
multiplications, assuming that
n
∈
N
p
1is
B
-smooth. This is of course the drawback to this algorithm, namely,
that it requires
n
to have a prime factor
p
such that
p
−
−
1 has only “small”
prime factors.
1 method was given by Lenstra
using elliptic curves, which we will study later in this appendix. In the Elliptic
curve algorithm, we will see that success in factoring depends upon an integer
“close” to
p
having only small prime factors, which is less demanding than
the
p
A generalization of the
p
−
−
1 algorithm and therefore more likely to occur. Another improvement
Search WWH ::
Custom Search