Cryptography Reference
In-Depth Information
n
-torsion points come from the line
ω
2
R
, hence lie in the subgroup generated
by
n
ω
2
,so
℘
(
n
ω
2
) must be an integer. If
n
is even and
z
1
C
/
(
Z
ω
1
+
Z
ω
2
)
has order
n
,then
z
generates the same subgroup of
C
/
(
Z
ω
1
+
Z
ω
2
)asoneof
1
∈
n
ω
2
+
2
ω
1
+
2
ω
2
. Therefore, if there is a torsion point
of order
n
, then at least one of these three values of
z
must yield an integral
value of
x
=
℘
(
z
).
The strategy is therefore to evaluate
℘
(
1
1
n
ω
2
+
2
ω
1
or
1
n
ω
2
or
n
ω
2
)if
n
is odd or if 4
x
3
+4
Ax
+4
B
has only one real root
℘
(
1
℘
(
1
n
ω
2
+
1
℘
(
1
n
ω
2
+
1
2
ω
1
+
1
n
ω
2
)
,
2
ω
2
)
if
n
is even and 4
x
3
+4
Ax
+4
B
has 3 real roots
2
ω
1
)
,
for each divisor of
b
, starting with the largest
n
. If we find a numerical value
of
x
that is close to an integer, we test whether
y
2
=
x
3
+
Ax
+
B
yields
an integral value of
y
. It can be checked whether or not (
x, y
) has order
n
by computing
n
(
x, y
). If so, then (since
n
is the largest divisor of
b
not yet
excluded), we have the largest cyclic subgroup of the torsion group. Since
only the 2-torsion can be noncyclic (Corollary 3.13), we need to see only if
there is a point of order 2 not already in the subgroup generated by (
x, y
).
If
n
(
x, y
)
,wecontinuewith
n
and smaller divisors that are still allowed
by Mazur's theorem and the value of
b
. We thus obtain all torsion points in
E
(
Q
).
The AGM method (Theorem 9.24) calculates
ω
1
and
ω
2
quickly. The fol-
lowing allows us to compute
℘
.
=
∞
PROPOSITION 9.35
Let
z ∈
C
and let
u
=
e
2
πiz/ω
2
.Let
τ
=
ω
1
/ω
2
(w iththe requirem en t that
τ
isinthe upper halfplane) and let
q
=
e
2
πiτ
.Then
℘
(
z
)=
2
πi
ω
2
2
1
12
+
q
n
)
2
.
q
n
u
)
2
+
∞
u
u
u
2
q
n
u
)
2
+
u
)
2
−
(1
−
(1
−
(
q
n
−
(1
−
n
=1
PROOF
Let
f
(
z
) denote the right-hand side of the equation. Since
|q| <
1,
it is easy to see that the series defining
f
(
z
) converges uniformly on compact
subsets of
C
that do not contain points in the lattice
ω
1
Z
+
ω
2
Z
. Therefore,
f
(
z
) is analytic away from these lattice points. Moreover, it has a double pole
at each lattice point. Using the fact that
u
=1+(2
πi/ω
2
)
z
+
, we find
that the Laurent expansion of
f
(
z
) around
z
= 0 starts (1
/z
2
)+
···
.
Since
u
is invariant under
z → z
+
ω
2
,sois
f
(
z
). Changing
z
to
z
+
ω
1
multiplies
u
by
q
. A straightforward calculation shows that
f
is invariant
under
u → qu
. Therefore
f
is doubly periodic.
The difference
f
(
z
)
−℘
(
z
) is a doubly periodic function with no poles except
possibly simple poles at the lattice points. By Theorem 9.1, this implies that
···
Search WWH ::
Custom Search