Cryptography Reference
In-Depth Information
Algorithm 27
Elkies' algorithm. (Source code provided by Drew Sutherland.)
INPUT:
A,B
∈ k
,
>
2,
j,
˜
∈ k
OUTPUT:
A, B,ψ
(
x
)
1:
Compute
φ
x
,
φ
y
,
φ
xx
,
φ
yy
and
φ
xy
Compute
A
and
B
18
B/A
,let
j
=
j
/
(1728
2:
Let
m
=
mj
, and let
k
=
−
j
)
˜
/
˜
, and let
k
3:
Let ˜
=−
j
φ
x
/
(
φ
y
), let
m
˜
/
(1728
=
=
−
˜
)
4:
Let
A
mk/
48 and
B
m
2
k/
864
4
6
=
=
(
j
2
φ
xx
+
2
j
˜
φ
xy
+
2
˜
2
φ
yy
)
/
(
j
φ
x
)
5:
Let
r
=−
Compute
p
1
k
)
/
4
6:
Let
p
1
=
(
r/
2
+
(
k
−
+
(
m
−
m
)
/
3)
7:
Let
d
=
(
−
1)
/
2
Compute the power sums
t
n
of the roots of
ψ
(
x
)
A
)
/
30, and
t
3
=
8:
Let
t
0
=
d
,
t
1
=
p
1
/
2,
t
2
=
−
−
−
−
−
((1
10
d
)
A
((1
28
d
)
B
42
t
1
A
B
)
/
70
9:
Let
c
0
=
0,
c
1
=
6
t
2
+
2
At
0
,
c
2
=
10
t
3
+
6
At
1
+
4
Bt
0
10:
for
n
=
2to
d
−
1
do
=
n
−
1
Let
s
i
=
1
c
i
c
n
−
i
11:
Let
12:
3
s
−
(2
n
−
1)(
n
−
1)
Ac
n
−
1
−
(2
n
−
2)(
n
−
2)
Bc
n
−
2
c
n
+
1
=
(
n
−
1)(2
n
+
5)
13:
end for
14:
for
n
=
3to
d
−
1
do
Let
15:
c
n
−
(4
n
−
2)
At
n
−
1
−
(4
n
−
4)
Bt
n
−
2
t
n
+
1
=
4
n
+
2
16:
end for
17:
Let
s
0
=
1
Compute the symmetric functions
s
n
of the roots of
ψ
(
x
)
18:
for
n
=
1to
d
do
Let
s
n
=
−
n
i
=
1
(
1)
i
t
i
s
n
−
i
−
19:
20:
end for
21:
return
ψ
(
x
)
=
i
=
0
(
1)
i
s
i
x
d
−
i
−
) is non-zero but small compared with
, due to divisions by small integers arising in the power series expansions for the mod-
ular functions. Algorithms for the case of small characteristic will be mentioned in Sec-
tion
25.2.3
.
A number of calculations can fail when char(
k
25.2.2 Stark's algorithm
Stark [
522
] gave a method to compute the rational function giving the
x
-coordinate of an
endomorphism
φ
:
E
→
E
corresponding to a complex number
β
(interpreting End(
E
)as
a subset of
C
). The idea is to use the fact that, for an elliptic curve
E
over the complex
