Cryptography Reference
In-Depth Information
12.4 Elliptic curve method
Let
N
be an integer to be factored and let
p
|
N
be prime. One can view Pollard's
p
−
1
method as using an auxiliary group (namely,
G
m
(
F
p
)) that may have smooth order. The
idea is then to obtain an element modulo
N
(namely,
a
B
!
), that is congruent modulo
p
(but
not modulo some other prime
q
N
) to the identity element of the auxiliary group.
Lenstra's idea was to replace the group
G
m
in the Pollard
p
|
1 method with the group
of points on an elliptic curve. The motivation was that even if
p
−
−
1 is not smooth it is
reasonable to expect that there is an elliptic curve
E
over
F
p
) is rather
smooth. Furthermore, since there are lots of different elliptic curves over the field
F
p
such that #
E
(
F
p
we
have a chance to split
N
by trying the method with lots of different elliptic curves. We refer
to Section
9.14
for some remarks on elliptic curves modulo
N
.
If
E
is a “randomly chosen” elliptic curve modulo
N
with a point
P
on
E
modulo
N
then
one hopes that the point
Q
[
B
!]
P
is congruent modulo
p
(but not modulo some other
prime
q
) to the identity element. One constructs
E
and
P
together, for example choosing
1
<x
P
,y
P
,a
4
<N
and setting
a
6
=
=
y
P
−
x
P
−
(
x
:
y
:
z
) using inversion-free arithmetic and projective coordinates (as in Exercise
9.1.5
) then
Q
a
4
x
P
(mod
N
). If one computes
Q
=
≡
O
E
(mod
p
) is equivalent to
p
|
z
. Here we are performing elliptic curve arithmetic
over the ring
(see Section
9.14
).
The resulting algorithm is known as the
elliptic curve method
or
ECM
and it is very
widely used, both as a general-purpose factoring algorithm in computer algebra packages,
and as a subroutine of the number field sieve. An important consequence of Lenstra's
suggestion of replacing the group
Z
/N
Z
F
p
by
E
(
F
p
) is that it motivated Miller and Koblitz to
F
p
for public key cryptography.
Algorithm
11
gives a sketch of one round of the ECM algorithm. If the algorithm fails
then one should repeat it, possibly increasing the size of
B
. Note that it can be more efficient
to compute [
B
!]
P
as a single exponentiation rather than a loop as in line 5 of Algorithm
11
;
see [
47
].
suggest using
E
(
F
p
) instead of
Algorithm 11
Elliptic curve factoring algorithm
INPUT:
N
∈ N
OUTPUT: Factor of
N
1:
Choose a suitable value for
B
2:
Choose random elements 0
≤
x,y,a
4
<N
y
2
x
3
3:
Set
a
6
=
−
−
a
4
x
(mod
N
)
4:
Set
P
=
(
x
:
y
:1)
5:
for
i
=
2to
B
do
Compute
P
=
[
i
]
P
6:
7:
end for
8:
return
gcd(
N,z
) where
P
=
(
x
:
y
:
z
)
