Cryptography Reference
In-Depth Information
Proof
The main loop is repeated
B
times and contains an exponentiation modulo
N
to a
power
i<B
. The cost of the exponentiation is
O
(log(
B
)
M
(log(
N
))) bit operations.
The algorithm is therefore exponential in
B
and so is only practical if
B
is relatively small.
If
B
O
(log(
N
)
i
) then the algorithm is polynomial-time. Unfortunately, the algorithm
only splits numbers of a special form (namely, those for which there is a factor
p
such that
p
=
−
1 is very smooth).
Exercise 12.3.6
Show that searching only over prime power values for
i
in Algorithm
10
lowers the complexity to
O
(
BM
(log(
N
))) bit operations.
It is usual to have a
second stage
or
continuation
to the Pollard
p
−
1 method. Suppose
that Algorithm
10
terminates with gcd(
b
−
1
,N
)
=
1. If there is a prime
p
|
N
such that
p
SQ
where
S
is
B
-smooth and
Q
is prime then the order of
b
modulo
p
is
Q
.
One will therefore expect to split
N
by computing gcd(
b
Q
(mod
N
)
−
1
=
1
,N
). The second
stage is to find
Q
if it is not too big. One therefore chooses a bound
B
>B
and wants to
compute gcd(
b
Q
(mod
N
)
−
B
.
We give two methods to do this: the standard continuation (Exercise
12.3.7
) has the same
complexity as the first stage of the
p
−
1
,N
) for all primes
B<Q
≤
1 method, but the constants are much better; the FFT
continuation (Exercise
12.3.8
) has better complexity and shows that if sufficient storage is
available then one can take
B
to be considerably bigger than
B
. Further improvements are
given in Sections 4.1 and 4.2 of Montgomery [
392
].
−
Exercise 12.3.7
(Standard continuation) Show that one can compute gcd(
b
Q
(mod
N
)
−
B
in
O
((
B
−
1
,N
) for all primes
B<Q
≤
B
)
M
(log(
N
))) bit operations.
=
√
B
−
Exercise 12.3.8
(Pollard's FFT continuation) Let
w
B
. We will exploit the
fact that
Q
w
(thisisverysim-
ilar to the baby-step-giant-step algorithm; see Section
13.3
). Let
P
(
x
)
=
B
+
vw
−
u
for some 0
≤
u<w
and some 1
≤
v
≤
=
w
−
1
i
=
0
−
b
i
)(mod
N
), computed as in Section
2.16
. Now compute gcd(
P
(
g
B
+
vw
)(mod
N
)
,N
)
for
v
(
x
=
1
,
2
,...,w
. For the correct value
v
we have
g
u
)
i
P
(
g
B
+
vw
)
(
g
B
+
vw
g
i
)
(
g
B
+
vw
(
g
B
+
vw
g
i
)
=
−
=
−
−
i
=
u
1)
i
=
u
g
u
(
g
B
+
vw
−
u
(
g
B
+
vw
g
i
)
.
=
−
−
Since
g
B
+
vw
−
u
1(mod
p
) then gcd(
P
(
g
B
+
vw
)(mod
N
)
,N
) is divisible by
p
.
Show that the time com
pl
exity of this continutation is
O
(
M
(
w
) log(
w
)
M
(log(
N
)), which
g
Q
=
≡
asymptotically is
O
(
√
B
log(
B
)
2
log(l
og(
B
))
M
(log(
N
))) bit operations. Show that the
storage required is
O
(
w
log(
w
))
O
(
√
B
log(
B
)) bits.
=
Exercise 12.3.9
The
p
+
1 factoring method uses the same idea as the
p
−
1 method but in
the algebraic group
T
2
or the algebraic group quotient corresponding to Lucas sequences.
Write down the details of the
p
+
1 factoring method using Lucas sequences.
