Cryptography Reference
In-Depth Information
12.3 The
p
−
1
factoring method
First we recall the notion of a smooth integer. These are discussed in more detail in
Section
15.1
.
=
r
i
=
1
p
e
i
Definition 12.3.1
Let
N
∈ N
(where we assume the
p
i
are distinct primes and
i
e
i
≥
1) and let
B
∈ N
. Then
N
is
B
-smooth
if all
p
i
≤
B
and
N
is
B
-power smooth
(or
strongly
B
-smooth
)ifall
p
e
i
i
≤
B
.
2
4
Example 12.3.2
528
=
·
3
·
11 is 14-smooth but is not 14-power smooth.
1 method was published by Pollard [
435
].
1
The
p
−
The idea is to suppose that
N
has prime factors
p
and
q
where
p
−
1is
B
-power smooth but
q
−
1 is not
B
-power
smooth. Then if 1
<a<N
is randomly chosen we have
a
B
!
≡
1(mod
p
) and, with high
probability,
a
B
!
1(mod
q
). Hence, gcd(
a
B
!
≡
−
1
,N
) splits
N
. Algorithm
10
gives the
Pollard
p
−
1 algorithm.
Example 12.3.3
Let
N
=
124639 and let
B
=
8. Choose
a
=
2. One can check that
gcd(
a
B
!
(mod
N
)
−
1
,N
)
=
113
from which one deduces that
N
1103.
This example worked because the prime
p
=
113
·
2
4
=
113 satisfies
p
−
1
=
·
7
|
8! and so
2
8!
≡
1(mod
p
) while the other prime satisfies
q
−
1
=
2
·
19
·
29, which is not 8-smooth.
Of course, the “factor” returned from the gcd may be 1 or
N
. If the factor is not 1 or
N
then we have split
N
as
N
ab
. We now test each factor for primality and attempt to split
any composite factors further.
=
Algorithm 10
Pollard
p
−
1 algorithm
INPUT:
N
∈ N
OUTPUT: Factor of
N
1:
Choose a suitable value for
B
2:
Choose a random 1
<a<N
3:
b
=
a
4:
for
i
=
2to
B
do
b
i
(mod
N
)
b
=
5:
6:
end for
7:
return
gcd(
b
−
1
,N
)
Exercise 12.3.4
Factor
N
=
10028219737 using the
p
−
1 method.
Lemma 12.3.5
The complexity of Algorithm
10
is O
(
B
log(
B
)
M
(log(
N
)))
bit operations.
1
According to [
567
], the first stage of the method was also known to D. N. Lehmer and D. H. Lehmer, though they never
published it.
