Cryptography Reference
In-Depth Information
9.14 Elliptic curves over rings
The elliptic curve factoring method (and some other theoretical applications in cryp-
tography) use elliptic curves over the ring
=
i
=
1
p
i
is square-free
5
one can use the Chinese remainder theorem to interpret a triple (
x,y,z
) such that
y
2
z
Z
/N
Z
. When
N
a
3
yz
2
x
3
a
2
x
2
z
a
4
xz
2
a
6
z
3
+
a
1
xyz
+
≡
+
+
+
(mod
N
) as an element of the direct
i
sum
F
p
i
) of groups of elliptic curves over fields. It is essential to use the projec-
tive representation, since there can be points that are the point at infinity modulo
p
1
but
not the point at infinity modulo
p
2
(in other words,
p
1
|
⊕
1
E
(
=
z
but
p
2
z
). Considering triples
(
x,y,z
) such that gcd(
x,y,z
)
1 (otherwise, the point modulo some prime is (0
,
0
,
0))
up to multiplication by elements in (
=
Z
Z
)
∗
leads to a projective elliptic curve point in
/N
Z
Z
E
(
). The usual formulae for the group operations can be used modulo
N
and, when
they are defined, give a group law. We refer to Section 2.11 of Washington [
560
]fora
detailed discussion, including a set of formulae for all cases of the group law. For a more
theoretical discussion we refer to Lenstra [
339
,
340
].
/N
5
The non-square-free case is more subtle. We do not discuss it.
