Cryptography Reference
In-Depth Information
Exercise 12.4.1
Show that the complexity of Algorithm
11
is
O
(
B
log(
B
)
M
(log(
N
))) bit
operations.
Exercise
12.4.2
Show
that
the
complexity
of
Algorithm
11
can
be
lowered
to
O
(
BM
(log(
N
))) bit operations using the method of Exercise
12.3.6
.
1 method (such as the standard
continuation, though not Pollard's FFT continuation) also apply directly to the elliptic
curve method. We refer to Section 7.4 of [
150
] for details. One can also employ all known
techniques to speed up elliptic curve arithmetic. Indeed, the Montgomery model for elliptic
curves (Section
9.12.1
) was discovered in the context of ECM rather than ECC (elliptic
curve cryptography).
In practice, we repeat the algorithm a number of times for random choices of
B,x,y
and
a
4
. The difficult problems are to determine a good choice for
B
and to analyse the
probability of success. We discuss these issues in Section
15.3
where we state Lenstra's
conjecture that the elliptic curve method factors integers in subexponential time.
Many of the techniques used to improve the Pollard
p
−
12.5 Pollard-Strassen method
Pollard [
435
] and, independently, Strassen gave a deterministic algorithm to factor an integer
N
in
O
(
N
1
/
4
) bit operations. It is based on the idea
2
of Section
2.16
; namely, that one can
evaluate a polynomial of degree
n
in (
Z
/N
Z
)[
x
]at
n
values in
O
(
M
(
n
) log(
n
)) operations
in
Z
. A different factoring algorithm with this complexity is given in Exercise
19.4.7
.
The trick to let
B
/N
Z
N
1
/
4
=
,
F
(
x
)
=
x
(
x
−
1)
···
(
x
−
B
+
1) (which has degree
B
) and to compute
F
(
jB
)(mod
N
)for1
≤
j
≤
B
. Computing these values requires
O
(
N
1
/
4
log(
N
)
3
log(log(
N
))
2
log(log(log(
N
)))) bit opera-
tions. Once this list of values has been computed, one computes gcd(
N,F
(
jB
)(mod
N
))
until one finds a value that is not 1. This will happen, for some
j
, since the smallest prime
factor of
N
is of the form
jB
O
(
M
(
B
) log(
B
)
M
(log(
N
)))
=
−
i
for some 1
≤
j
≤
B
and some 0
≤
i<B
. Note that
M
gcd(
N,F
(
jB
)(mod
N
)) may not be prime, but one can find the prime factors of it in
O
(
N
1
/
4
) bit operations by computing gcd(
M,jB
=
−
i
) for that value of
j
and all 0
≤
i<B
.
Indeed, one can find all prime factors of
N
that are less than
N
1
/
2
(and hence factor
N
O
(
N
1
/
4
) bit operations.
completely) using this method. The overall complexity is
O
(
N
1
/
6
)
Show that one can determine all primes
p
such that
p
2
Exercise 12.5.1
|
N
in
bit operations.
2
Despite the title of this chapter, the Pollard-Strassen algorithm does not use algebraic groups or any group-theoretic property
of the integers modulo
N
.
