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