Cryptography Reference
In-Depth Information
in a nutshell, is to also store “nearly smooth” relations (i.e., elements that are the product
of a smooth element with one or two prime elements that are not too large) and perform
some elimination of these “large primes” before doing the main linear algebra stage (this
is similar to, but more efficient than, taking a larger factor base). Finally, we remark that
the first stage of these algorithms (i.e., collecting relations) can always be distributed or
parallelised.
15.3 Elliptic curve method revisited
We assume throughout this section that
N
is an integer to be factored and that
N
is
odd, composite and not a perfect power. We denote by
p
the smallest prime factor of
N
.
The elliptic curve method works well in practice but, as with the Pollard
p
∈ N
1 method,
its complexity depends on the size of the smallest prime dividing
N
. It is not a polynomial-
time algorithm because, for any constant
c>
0 and over all
N
and
p
−
|
N
, a randomly chosen
F
p
is not likely to have
O
(log(
N
)
c
)-smooth order. As we have seen, the
theorem of Canfield, Erdos and Pomerance says it is more reasonable to hope that integers
have a subexponential probability of being subexponentially smooth. Hence, one might
hope that the elliptic curve method has subexponential complexity. Indeed, Lenstra [
339
]
makes the following conjecture (which is essentially that the Canfield-Erdos-Pomerance
result holds in small intervals).
elliptic curve over
Conjecture 15.3.1
(Lenstra [
339
], page 670)
T
he prob
ab
ility that an integer, chosen
uniformly at random in the range
(
X
−
√
X,X
+
√
X
)
,isL
X
(1
/
2
,c
)
-smooth is
o
(1))
as X tends to infinity.
5
L
X
(1
/
2
,
−
1
/
(2
c
)
+
One can rephrase Conjecture
15.3.1
as saying that if
p
s
is the probability tha
t
a random
integer between 1 and
X
is
Y
-smooth then
(
X
2
√
X,Y
)
2
√
Xp
s
.More
+
−
(
X,Y
)
≈
generally, one would like to know that, for sufficiently large
6
X,Y
and
Z
,
+
−
∼
(
X
Z,Y
)
(
X,Y
)
Z
(
X,Y
)
/X
(15.5)
or, in other words, that integers in a short interval at
X
are about as likely to be
Y
-smooth
as integers in a large interval at
X
.
We now briefly summarise some results in this area; see Granville [
243
] for details and
references. Harman (improved by Lenstra, Pila and Pomerance [
342
]) showed, for any fixed
β>
1
/
2 and
X
exp(log(
X
)
2
/
3
+
o
(1)
), where the
o
(1) is as
X
≥
Y
≥
→∞
, that
X
β
,Y
)
(
X
+
−
(
X,Y
)
>
0
.
Obtaining
re
sults for the required value
β
1
/
2 seems to be hard and the experts refer
to the “
√
X
barrier” for smooth integers in short intervals. It is known that this barrier
=
Lenstra considers the subinterval (
X
−
√
X,X
+
√
X
) of the Hasse interval [
X
+
1
−
2
√
X,X
+
1
+
2
√
X
] because the
distribution of isomorphism classes of randomly chosen elliptic curves is relatively close to uniform when restricted to those
whose group order lies in this subinterval. In contrast, elliptic curves whose group orders are near the edge of the Hasse interval
arise with lower probability.
5
6
The notation
∼
means taking a limit as
X
→∞
, so it is necessary that
Y
and
Z
grow in a controlled way as
X
does.
