<<

. 4
( 10)



>>


when P1 = P2 , and
X3 = Y1 (X1 ’ Z1 ), Y3 = X1 (Z1 ’ Y13 ), Z3 = Z1 (Y13 ’ X1 )
3 3 3 3


otherwise. The formul¦ for adding two (distinct) points and for doubling a
point appear to be di¬erent. However, the doubling operation can be rewrit-
ten in terms of a (general) addition operation. This is stated in the following
lemma.
Lemma V.1 ([188]). If P1 = (X1 : Y1 : Z1 ) is a point on an Hessian elliptic
curve, then
[2](X1 : Y1 : Z1 ) = (Z1 : X1 : Y1 ) + (Y1 : Z1 : X1 ) .
Furthermore, we have (Z1 : X1 : Y1 ) = (Y1 : Z1 : X1 ).
The correctness of the above lemma is easily veri¬ed. Let T1 = (0 : ’1 : 1)
and T2 = ’T1 = (’1 : 0 : 1) denote the two points of order 3 on H. We
have [2](X1 : Y1 : Z1 ) = ((X1 : Y1 : Z1 ) + T1 ) + ((X1 : Y1 : Z1 ) + T2 ) = (Z1 :
X1 : Y1 ) + (Y1 : Z1 : X1 ). Moreover, (Z1 : X1 : Y1 ) = (Y1 : Z1 : X1 ) implies
T1 = T2 , a contradiction.


V.2.2.2. Jacobi Form. When an elliptic curve contains a copy of Z/2Z
(which implies that its group order is a multiple of 2), it can be represented
by the (extended) Jacobi form [27]
J : Y 2 = X 4 ’ 2δX 2 Z 2 + Z 4 . (V.6)
1
The construction given in [309] assumes that p ≡ 2 (mod 3).
V.2. INDISTINGUISHABLE POINT ADDITION FORMULÆ 91

Let P1 = (X1 : Y1 : Z1 ) and P2 = (X2 : Y2 : Z2 ) denote points on the
Jacobi curve J. The inverse of P1 is ’P1 = (’X1 : Y1 : Z1 ), and the sum
P3 = P1 + P2 is de¬ned as (X3 : Y3 : Z3 ) with
X3 = X1 Z1 Y2 + Y1 X2 Z2 , Z3 = (Z1 Z2 )2 ’ (X1 X2 )2 ,
Y3 = (Z3 + 2 (X1 X2 )2 )(Y1 Y2 ’ 2δX1 X2 Z1 Z2 ) +
22 22
2 X1 X2 Z1 Z2 (X1 Z2 + Z1 X2 ) .
It is worth noting the same formula applies for adding (distinct) points or for
doubling a point.
Finally, when the curve contains a copy of (Z/2Z) — (Z/2Z), the Jacobi
curve equation (V.6) can be rescaled, in most cases, to the value = 1 [27].
This corresponds exactly to the Jacobi curves initially suggested by Liardet
and Smart [220] but represented as the intersection of two quadrics.2

The di¬erent costs for point addition formul¦ are summarized in Ta-
ble V.1. Symbols M and C, respectively, stand for the cost of ¬eld multipli-
cation and multiplication by a constant. The costs given for the Weierstraß
form consider the short curve equation Y 2 Z = X 3 + a4 XZ 2 + a6 Z 3 .
Table V.1. Point Addition for Elliptic Curves over Fp , p > 3

Parameterization Cost Cofactor
Weierstraß form [51] 17M + 1C (general case)

16M + 1C (a4 = ’1)
(with uni¬ed formul¦)
h∝3
Hessian form [188] 12M
h∝2
Extended Jacobi form [27] 13M + 3C (general case)
h∝4
13M + 1C ( = 1)
© of 2 quadrics [220] h∝4
16M + 1C

Elliptic curve standards ([IEEE 1363, FIPS 186.2, SECG]) recom-
mend the use of elliptic curves with group order #E = h · q, where q is
a prime and the cofactor h is ¤ 4.
V.2.3. Dummy Operations. Point addition formul¦ need not be strictly
equivalent. It su¬ces that the di¬erent point additions cannot be distin-
guished by side-channel analysis. This can be achieved by inserting dummy
(¬eld) operations. Such a technique is of particular interest when the costs
for adding two (distinct) points and for doubling a point are similar, as is the
case for elliptic curves de¬ned over binary ¬elds [76].
Consider the (non-supersingular) elliptic curve over F2n given by the short
Weiertraß equation
Ea2 ,a6 : y 2 + xy = x3 + a2 x2 + a6 .
2
The construction given in [220, 27] works whenever p ≡ 3 (mod 4) and with a 7/8
probability when p ≡ 1 (mod 4).
92 V. DEFENCES AGAINST SIDE-CHANNEL ANALYSIS

The slope » given in Eq. (V.3) becomes
y1 + y2 y1
»= when x1 = x2 , and » = x1 + when x1 = x2 .
x1 + x2 x1
In terms of ¬eld operations, the expression for » is almost the same for
adding or doubling points. The next algorithm (Algorithm V.1) details how
inserting two dummy (¬eld) additions allows us to double a point in a way
similar to the addition of two distinct points. We assume that registers con-
tain ¬eld elements and that registers T0 , T1 , T2 , T3 are initialized with the
coordinates of points P1 and P2 being added.
Remark. It is implicitly assumed [as well as in all algorithms presented in
this chapter] that the loading/storing of random values from di¬erent registers
is indistinguishable. A possible solution is presented in [234] when this latter
assumption is not veri¬ed. See also [176] and Section V.4.

Algorithm V.1: Point Addition (with Dummy Operations)

Points P1 = (x1 , y1 ) and P2 = (x2 , y2 ) ∈ Ea2 ,a6 (F2n ), P1 = ’P2 ;
INPUT:
registers (T0 , T1 ) ← P1 and (T2 , T3 ) ← P2 .
OUTPUT: The sum P1 + P2 or [2]P1 .
Addition: P1 ← P1 + P2 Doubling: P1 ← [2]P1
1. T0 ← T0 + T2 T5 ← T0 + T2
(= x1 + x2 ) (fake).
2. T1 ← T1 + T3 T5 ← T2 + T5
(= y1 + y2 ) (= x1 ).
3. T4 ← T1 /T0 T4 ← T1 /T0
(= ») (= y1 /x1 ).
4. T0 ← T0 + T4 T4 ← T0 + T4 (= »).
5. T5 ← T4 T0 ← T4
2 2
2
(= »2 ).
(= » )
6. T5 ← T5 + a2 T0 ← T0 + a2
(= »2 + a2 ) (= »2 + a2 ).
7. T0 ← T0 + T5 T0 ← T0 + T4
(= x3 ) (= x3 ).
8. T1 ← T0 + T3 T1 ← T0 + T1
(= x3 + y2 ) (= x3 + y1 ).
9. T5 ← T0 + T2 T5 ← T0 + T5
(= x2 + x3 ) (= x1 + x3 ).
10. T4 ← T4 · T5 T4 ← T4 · T5 .
11. T1 ← T1 + T4 T1 ← T1 + T4
(= y3 ) (= y3 ).
12. Return (T0 , T1 ).

Hence, Algorithm V.1 only requires one inversion, two multiplies and one
squaring for adding or doubling points, in an indistinguishable fashion, on a
(non-supersingular) elliptic curve over F2n .

V.3. Regular Point Multiplication Algorithms
Point addition formul¦ may have di¬erent side-channel traces, provided
that they do not leak information about k in the point multiplication algo-
rithm used for evaluating Q = [k]P . For binary algorithms, this implies that
the processing of bits “0” and bits “1” of multiplier k are indistinguishable.
V.3. REGULAR POINT MULTIPLICATION ALGORITHMS 93

V.3.1. Classical Algorithms. The usual trick for removing the condi-
tional branching in the double-and-add algorithm (i.e., the additively written
square-and-multiply algorithm) consists in performing a dummy point addi-
tion when multiplier bit kj is zero. As a result, each iteration appears as
a point doubling followed by a point addition [87], as illustrated in Algo-
rithm IV.3. Note that a NAF-representation for k in Algorithm IV.3 does
not improve the performances. An algorithm using a NAF-representation is
presented in [171].

Another popular point multiplication algorithm was developed by Mont-
gomery [255] as a means for speeding up the ECM factoring method on a
special form of elliptic curves.


Algorithm V.2: Montgomery Point Multiplication Algorithm


’1
kj 2j , kj ∈ {0, 1}.
INPUT: Point P and -bit multiplier k = j=0
OUTPUT: Q = [k]P .
R0 ← P , R1 ← [2]P .
1.
For j = ’ 2 to 0 by ’1 do:
2.
R1’kj ← R0 + R1 .
3.
Rkj ← [2]Rkj .
4.
Return R0 .
5.


Algorithm V.2 behaves regularly [225, 264] but seems, at ¬rst glance, as
costly as the double-and-add-always algorithm. However, it does not need
to handle the y-coordinates: the sum of two points whose di¬erence is a
known point can be computed without the y-coordinates [255]. Note, that
the di¬erence R1 ’R0 remains invariant throughout Algorithm V.2 (and hence
is equal to P ). Further, the y-coordinate of a point R0 can be recovered
from a point P , the x-coordinate of R0 , and the x-coordinate R0 + P . The
y-coordinate of Q = [k]P can thus also be recovered when only x-coordinates
are used in the Montgomery point multiplication algorithm. The formul¦
for (general) elliptic curves over ¬elds of characteristic = 2, 3 can be found
in [51, 178, 120] and in [225] over binary ¬elds.
Montgomery point multiplication is particularly suited to elliptic curves
over binary ¬elds in a normal basis representation [ECC, Section II.2.2] as
each iteration globally amounts to only six (¬eld) multiplications. The algo-
rithm is due to L´pez and Dahab [225].
o
94 V. DEFENCES AGAINST SIDE-CHANNEL ANALYSIS




Algorithm V.3: Montgomery Multiplication (for Binary Curves)


Point P = (xP , yP ) ∈ Ea2 ,a6 (F2n ) and
INPUT:
’1
-bit multiplier k = j=0 kj 2j , kj ∈ {0, 1}.
OUTPUT: xQ = x([k]P ).
Z0 ← 1, X0 ← xP , Z1 ← xP 2 , X1 ← Z1 2 + a6 .
1.
For j = ’ 2 to 0 by ’1 do:
2.
T0 ← X0 · Z1 , T1 ← X1 · Z0 .
3.
Z1’kj ← (T0 + T1 )2 , X1’kj ← xP · Z1’kj + T0 · T1 .
4.
T0 ← Zkj2 , T1 ← Xkj2
5.
Zkj ← T0 · T1 , Xkj ← T1 2 + a6 · T0 2 .
6.
Return X0 /Z0 .
7.


Some applications require both the x- and y-coordinates of point Q = [k]P .
At the end of Algorithm V.3, registers X1 and Z1 , respectively, contain the val-
ues of the projective X- and Z-coordinates of point [k+1]P . The y-coordinate
of Q can then be recovered as

(xQ + xP )[(xQ + xP )(X1 /Z1 + xP ) + x2 + yP ]
P
yQ = + yP .
xP



V.3.2. Atomic Algorithms. The idea behind the double-and-add-always
algorithm (Algorithm IV.3) is to remove the conditional branching in the basic
double-and-add algorithm so that each iteration appears as a point doubling
followed by a point addition. This idea was later generalized and extended
by Chevallier-Mames, Ciet and Joye, resulting in the concept of side-channel
atomicity [76].
There is a better option than the double-and-add-always algorithm when
point doubling and point addition are indistinguishable by side-channel anal-
ysis (see Section V.2). In this case, the conditional branching can be removed
so that the whole point multiplication algorithm appears as a regular repeti-
tion of point additions. By doing so, we obtain the atomic double-and-add
algorithm [76]. As a side-e¬ect, such an algorithm leaks the Hamming weight
of multiplier k. While this is generally not an issue (see however [61]), the
Hamming weight can be masked using standard multiplier randomization
techniques (see Section V.5).
V.3. REGULAR POINT MULTIPLICATION ALGORITHMS 95



Algorithm V.4: Atomic Double-and-Add Algorithm
’1
kj 2j , kj ∈ {0, 1}.
INPUT: Point P and -bit multiplier k = j=0
OUTPUT: Q = [k]P .
1. R0 ← P , R1 ← P , j ← ’ 2, b ← 0.
2. While (j ≥ 0) do:
R0 ← R0 + Rb .
3.
b ← b • kj , j ← j + kj ’ 1.
4.
5. Return R0 .

The above algorithm assumes that (i) xor-ing kj with bit b, and (ii) adding
kj to j ’ 1 does not leak information about multiplier bit kj . If so, again
randomization techniques allow us to mask the value of kj . For example,
b • kj can be evaluated as b • (kj • r) • r for a random bit r, and j + kj ’ 1
can be evaluated as j + (kj + t) ’ (t + 1) for a random integer t.
If needed, point addition and point subtraction formul¦ can be adapted
so that they become indistinguishable. It is then advantageous to replace
the double-and-add algorithm with the double-and-add/subtract algorithm.
When the multiplier k is expressed as a NAF, this results in a 11.11% speed-
up factor [256], on average. It is easy to modify Algorithm V.4 to take as
input a signed representation for the multiplier k. For a signed digit kj ,
sgn(kj ) indicates whether kj is negative (i.e., sgn(kj ) = 1 if kj < 0 and 0
otherwise) and |kj | denotes the absolute value of kj . To ease the presentation,
“1 represents a point subtraction and “0 represents a point addition (i.e.,
P1 “1 P2 = P1 ’ P2 and P1 “0 P2 = P1 + P2 ).

Algorithm V.5: Atomic Double-and-Add/Subtract Algorithm
’1
kj 2j , kj ∈ {0, ’1, 1}.
INPUT: Point P and multiplier k = 2 + j=0
OUTPUT: Q = [k]P .
1. R0 ← P , R1 ← P , j ← ’ 1, b ← 0.
2. While (j ≥ 0) do:
σ ← b § sgn(kj ).
3.
R0 ← R0 “σ Rb .
4.
b ← b • |kj |, j ← j + b ’ 1.
5.
6. Return R0 .

Using the indistinguishable point addition formul¦ of Algorithm V.1, this
yields a very e¬cient algorithm for (non-supersingular) elliptic curves over
binary ¬elds. For elliptic curves over large prime ¬elds, the indistinguish-
able point addition formul¦ are somewhat costly, at least for general elliptic
curves (see Table V.1). Rather than considering point addition as an atomic
operation, we may look at the ¬eld level and express point addition and point
96 V. DEFENCES AGAINST SIDE-CHANNEL ANALYSIS

doubling as a regular repetition of ¬eld operations. With Jacobian coordi-
nates [ECC, Section IV.1.1], the a¬ne point P = (xP , yP ) corresponds to
the projective point (xp θ2 : yp θ3 : θ)J , for any non-zero ¬eld element θ, on
the projective Weierstraß form
Ea4 ,a6 : Y 2 = X 3 + a4 XZ 4 + a6 Z 6 .
Let P1 = (X1 : Y1 : Z1 )J and P2 = (X2 : Y2 : Z2 )J (with P1 , P2 = O and
P1 = ’P2 ) denote points on the above curve. The double of P1 is equal to
[2]P1 = (X3 : Y3 : Z3 )J with
X3 = M 2 ’ 2S, Y3 = M (S ’ X3 ) ’ T, Z3 = 2Y1 Z1 ,
where M = 3X1 + a4 Z1 , S = 4X1 Y12 , and T = 8Y14 ; and the sum of P1 and
2 4

P2 is equal to P3 = (X3 : Y3 : Z3 )J with
X3 = W 3 ’ 2U1 W 2 + R2 , Y3 = ’S1 W 3 + R(U1 W 2 ’ X3 ), Z3 = Z1 Z2 W,
2 2 3 3
where U1 = X1 Z2 , U2 = X2 Z1 , S1 = Y1 Z2 , S2 = Y2 Z1 , T = U1 + U2 ,
W = U1 ’ U2 , and R = S1 ’ S2 [236]. A careful analysis of the point addi-
tion formul¦ shows that point doubling and (true) point addition can both
be expressed as a succession of the following atomic block: one ¬eld multi-
plication followed by two ¬eld additions (along with a negation to possibly
perform a ¬eld subtraction) [76]. This allows us to obtain a regular point
multiplication without dummy ¬eld multiplication. The algorithm requires
matrices ((u0 )r,c )0¤r¤10 , ((u1 )r,c )0¤r¤10 and ((u2 )r,c )0¤r¤10 given by
0¤c¤9 0¤c¤15 0¤c¤15

«  « 
4 5 5 5 3 2 5 1 2 4 4 1 4 2 4 5 4 4 3 3 6 1 5 1 2 4
¬1 4· ¬9 4·
3 5 0 3 2 1 4 2 1 4 2 3 4 3 4 3 3 5 1 5 4 2
¬ · ¬ ·
¬1 5· ¬9 6·
3 5 5 5 2 2 4 2 4 9 4 3 7 4 8 9 5 5 6 6 4 5
¬ · ¬ ·
¬5 2· ¬5 2·
1 1 4 1 2 1 1 2 5 5 5 5 2 2 6 6 6 6 1 6 1 1
¬ · ¬ ·
¬4 2· ¬1 2·
1 1 4 1 2 1 1 2 1 1 1 1 2 2 5 5 5 3 1 1 1 1
¬ · ¬ ·
¬4 4· , ¬5 4·
(u0 ) = (u1 ) = ,
1 3 5 3 2 5 5 2 5 5 5 5 5 5 6 6 6 6 4 2 5 6
¬ · ¬ ·
¬3 2· ¬5 6·
3 3 3 3 4 5 4 3 5 5 5 5 5 6 4 6 6 3 4 2 6 3
¬ · ¬ ·
¬4 4· ¬5 6·
1 1 5 1 1 1 1 5 5 5 5 5 5 6 4 6 6 6 1 6 1 6
¬ · ¬ ·
¬4 4· ¬1 1·
¬ · ¬ ·
1 1 2 1 1 1 1 1 1 1 1 1 1 5 2 5 5 3 1 2 1 1
5 5 5 6
3 3 2 3 3 5 5 5 5 5 5 5 5 6 4 6 6 6 4 6 6 6
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
« 
4 1 4 2 4 5 4 4 3 3 6 1 5 1 2 4
¬9 4·
1 4 2 3 4 3 4 3 3 5 1 5 4 2
¬ ·
¬9 6·
4 9 4 3 7 4 8 9 5 5 6 6 4 5
¬ ·
¬5 2·
5 5 5 5 2 2 6 6 6 6 1 6 1 1
¬ ·
¬1 2·
1 1 1 1 2 2 5 5 5 3 1 1 1 1
¬ ·
¬5 4·
(u2 ) = .
5 5 5 5 5 5 6 6 6 6 4 2 5 6
¬ ·
¬5 6·
5 5 5 5 5 8 4 8 6 3 4 2 6 3
¬ ·
¬5 6·
5 5 5 5 5 6 4 6 6 6 1 6 1 6
¬ ·
¬1 1·
¬ ·
1 1 1 1 1 5 2 5 5 3 1 2 1 1
5 6
5 5 5 5 5 6 4 6 6 6 4 6 6 6
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
V.4. BASE-POINT RANDOMIZATION TECHNIQUES 97



Algorithm V.6: Atomic Point Multiplication (over Fp )

Point P = (XP : YP : ZP )J ∈ Ea4 ,a6 (Fp ),
INPUT:
’1
multiplier k = 2 + j=0 kj 2j , kj ∈ {0, ’1, 1}, and
matrices ((u0 )r,c )0¤r¤10 , ((u1 )r,c )0¤r¤10 and ((u2 )r,c )0¤r¤10 .
0¤c¤9 0¤c¤15 0¤c¤15
OUTPUT: Q = [k]P .
1. T0 ← a4 , T1 ← X1 , T2 ← Y1 , T3 ← Z1 , T7 ← X1 , T8 ← Y1 , T9 ← Z1 .
2. j ← ’ 1, b ← 0, s ← 0.
3. While (j ≥ 0) do:
σ ← b § sgn(kj ).
4.
c ← s · (c + 1), t ← b + σ.
5.
T(ut )0,c ← T(ut )1,c · T(ut )2,c , T(ut )3,c ← T(ut )4,c + T(ut )5,c .
6.
T(ut )6,c ← ’ T(ut )6,c , T(ut )7,c ← T(ut )8,c + T(ut )9,c .
7.
s ← T(ut )10,c .
8.
b ← (¬s) § (b • |kj |), j ← j + (b ∨ s) ’ 1.
9.
10. Return (T1 : T2 : T3 )J .

There are numerous variants of this algorithm, which may be more or less
appropriate and e¬cient for a given architecture.

V.4. Base-Point Randomization Techniques
What makes elliptic curves particularly fruitful for designing countermea-
sures is the ability to represent elements of the underlying group in many dif-
ferent, randomized ways while keeping a good computational e¬ciency. This
section presents a variety of strategies built on the mathematical structure
of the curves, which lead to e¬cient and simple techniques for randomizing
(the representation of) base-point P in the computation of Q = [k]P .
V.4.1. Point Blinding. The method is analogous to Chaum™s blind signa-
ture scheme for RSA [65]. Point P to be multiplied is “blinded” by adding a
secret random point R for which the value of S = [k]R is known. The point
multiplication, Q = [k]P , is done by computing the point [k](P + R) and
subtracting S to get Q. Points R and S = [k]R can be initially stored in-
side the device and refreshed at each new execution by computing R ← [r]R
and S ← [r]S, where r is a (small) random generated at each new execu-
tion [87, 205]. As R is secret, the representation of point P — = P + R is
unknown in the computation of Q— = [k]P — .
V.4.2. Randomized Projective Representations. In projective coordi-
nates, points are not uniquely represented. For example, in homogeneous co-
ordinates, the triplets (θXP : θYP : θZP ) with any θ = 0 represent the same
point; and similarly in Jacobian coordinates, the triplets (θ2 XP : θ3 YP : θZP )J
98 V. DEFENCES AGAINST SIDE-CHANNEL ANALYSIS

for any θ = 0 represent the same point. Other projective representations are
described in [77, 85].
Before each new execution of the point multiplication algorithm for com-
puting Q = [k]P , the projective representation of input point P is randomized
with a random non-zero value θ [87]. This makes it no longer possible to pre-
dict any speci¬c bit in the binary representation of P .
The randomization can also occur prior to each point addition or at ran-
dom during the course of the point multiplication algorithm.

V.4.3. Randomized Elliptic Curve Isomorphisms. Point P = (xP , yP )
on elliptic curve E is randomized as P — = φ(P ) on E — = φ(E), for a random
curve isomorphism φ. Then Q = [k]P is evaluated as Q = φ’1 ([k]P — ) [190],
or schematically,
mult. by k map
P ∈¦ ’’ ’ ’ ’ ’’
’’’’’’ Q = [k]P ∈ E(K)
E(K)
¦ ¦ ’1
¦φ
φ .
mult. by k map
P — ∈ E — (K) ’ ’ ’ ’ ’ ’ ’ Q— = [k]P — ∈ E — (K)
’’’’’’
More speci¬cally, for a random … ∈ K \ {0}, point P = (xP , yP ) on the
Weiertraß curve E given by Eq. (V.1) is mapped to point P — = (… 2 xP , … 3 yP )
on the isomorphic curve
E — : y 2 + (…a1 )xy + (… 3 a3 )y = x3 + (… 2 a2 )x2 + (… 4 a4 )x + … 6 a6 .
The next step consists of computing Q— = [k]P — on E — . If Q— = O, then
Q = O; otherwise, if Q— = (xQ— , yQ— ), then Q = (… ’2 xQ— , … ’3 yQ— ).

V.4.4. Randomized Field Isomorphisms. Here, given a point P on an
elliptic curve E de¬ned over a ¬eld K, a random ¬eld isomorphism κ : K ’ K—
is applied to P and E to get point P — = κ(P ) on E — = κ(E). Then, point
multiplication Q = [k]P is evaluated as κ’1 ([k]P — ) [190].

V.5. Multiplier Randomization Techniques
Analogously to Section V.4, this section reviews several strategies for ran-
domizing the computation of Q = [k]P but with a randomized (representation
of) multiplier k.

V.5.1. Multiplier Blinding. Let ord(P ) denote the order of point P ∈
E(K). We obviously have
[k]P = [k + r ord(P )]P
for any r. As a consequence, the multiplier k can be blinded as k — = k +
r ord(P ) for a random r and Q = [k]P can be computed as Q = [k — ]P .
Alternatively, since by Lagrange™s Theorem the order of an element always
divides the order of its group, we can randomize the multiplier k as k — =
V.5. MULTIPLIER RANDOMIZATION TECHNIQUES 99

k + r #E for a random r, where #E denotes the group order of elliptic
curve E [87, 205].
V.5.2. Multiplier Splitting. The multiplier k can also be decomposed into
two (or several) shares. The idea of splitting the data was already abstracted
in [64] as a general countermeasure against side-channel attacks.
— — —
Using an additive splitting, k is written as k = k1 + k2 , where k1 = r

and k2 = k ’ r for a random r. Then Q = [k]P is evaluated as Q =
— —
[k1 ]P + [k2 ]P [82]. To hide all the bits of multiplier k, the size of r should be
comparable to that of k. A possible direction to shorten the size of r consists
— — — —
of decomposing k as k = k1 r + k2 with k1 = k/r and k2 = k mod r, and
— —
evaluating Q as Q = [k1 ]R + [k2 ]P with R = [r]P .
We can also use a multiplicative splitting and evaluate Q = [k]P as Q =
’1
[kr ]([r]P ) for a random r invertible modulo ord(P ) [329].
V.5.3. Frobenius Endomorphism. The Koblitz elliptic curves (a.k.a. ano-
malous binary curves or ABC™s) [202] are the curves K0 and K1 over F2n given
by
Ka2 : y 2 + xy = x3 + a2 x2 + 1
with a2 ∈ {0, 1}. On such curves, the Frobenius endomorphism • maps a
point P = (x, y) to •(P ) = (x2 , y 2 ) ∈ Ka2 . Therefore, in the computation
of Q = [k]P , the scalar k can be written as a Frobenius expansion since
multiplication by k is an endomorphism and Z ⊆ Z[•] ⊆ End(Ka2 ).
The ring Z[•] is a Euclidean domain with respect to the norm N(r +s•) =
r + (’1)1’a2 rs + 2s2 . Furthermore, as N(•) = 2, every element r + s• in
2

Z[•] can be written as a •-NAF, that is,
with ki ∈ {’1, 0, 1} and ki · ki+1 = 0 .
ki •i
r + s• =
i

Unfortunately, the so-obtained Frobenius expansion is roughly twice the
length of the usual balanced binary expansion, and so, even if the evaluation
of • is very fast, it is not clear that the resulting method is faster. This
drawback was loopholed in [237, 316] with the following observation. We
obviously have •n = 1 and thus Q = [k ]P with k = k mod (•n ’ 1). As
N(•n ’ 1) = #Ka2 (F2n ) ≈ 2n by Hasse™s Theorem, the •-NAF expression of
k , k = i ki •i , would have a length approximatively equal to that of the
(usual) NAF expression of k.
This yields the following method for randomizing the multiplier k on
Koblitz curves [190]. For any nonzero ρ ∈ Z[•], k mod (ρ(•n ’ 1)) acts
identically on a point P ∈ Ka2 (F2n ) and so Q = [k]P can be evaluated as
κ— •i (P ),
i
i

where i κ— •i is the •-NAF expression of κ— and κ— = k mod (ρ(•n ’ 1)) for
i
a (short) non-zero random ρ ∈ Z[•].
100 V. DEFENCES AGAINST SIDE-CHANNEL ANALYSIS

For cryptographic applications, n is chosen prime and so #K0 (F2n ) = 4q
or #K1 (F2n ) = 2q for a prime q. In that case, when working in the subgroup
of order q, k can be reduced modulo ρ(•n ’1)/(•’1) [211]. See also [161] for
further randomization techniques dedicated to Koblitz curve cryptosystems
and [79] for similar randomization techniques on elliptic curves having non-
trivial e¬ciently computable endomorphisms.
V.6. Preventing Side-Channel Analysis
The general (software) methodology for preventing side-channel leakage
is a two-step process. The ¬rst step consists in making SPA-like attacks
impossible and the second step in making DPA-like attacks impossible.
SPA-like attacks are inapplicable when it is not possible to relate secret
data with a single execution of the cryptoalgorithm. For elliptic curve cryp-
tosystems, this implies that the value of k (or a part thereof) cannot be
recovered by monitoring the processing of Q = [k]P . Various techniques
towards this goal were presented in Sections V.2 and V.3.
To successively mount a DPA-like attack, an adversary should be able
to predict any relevant bit. Therefore, a proper randomization of the inputs
to the cryptoalgorithm yields an implementation secure against DPA-like at-
tacks. Several randomization techniques for base-point P and multiplier k in
the point multiplication Q = [k]P were presented in Sections V.4 and V.5,
respectively. The randomization should of course be e¬ective to prevent re-
¬ned attacks [151, 6] (cf. Section IV.5.4). As a general rule of thumb, both
P and k should be randomized in the computation of Q = [k]P .
Part 3

Mathematical Foundations
CHAPTER VI

Advances in Point Counting

F. Vercauteren

The preferred method for generating elliptic curves suitable for crypto-
graphic applications is to choose a large ¬nite ¬eld and to randomly select
curves over that ¬eld until one is found with nearly prime group order.
Let E be an elliptic curve over Fq , with q = pn . The number of Fq -rational
points #E(Fq ) satis¬es the relation #E(Fq ) = q+1’t, where t = Tr(F ) is the
trace of the Frobenius endomorphism F : E(Fq ) ’ E(Fq ) : (x, y) ’ (xq , y q ).

By Hasse™s theorem [307, Theorem V.1.1] we have |t| ¤ 2 q, so it su¬ces to

compute t modulo B with B > 4 q.
In 1985, Schoof [292] described the ¬rst polynomial time algorithm to
compute #E(Fq ) using an l-adic approach. The key idea of Schoof™s algo-
rithm is to compute t modulo su¬ciently many primes l such that l ≥ B.
The time complexity of Schoof™s algorithm is O(log3µ+2 q) and the space com-
plexity amounts to O(log3 q), with µ a constant such that multiplication of
two m-bit integers can be computed in O(mµ ) time. For example: µ = 2
for classical multiplication, µ = log2 3 for Karatsuba multiplication [194] and
µ = 1 + µ with µ ∈ R>0 for Sch¨nhage“Strassen [291] multiplication.
o
Several improvements mainly due to Elkies [115] and Atkin [11] resulted
in a heuristically estimated time complexity of O(log2µ+2 q) and space com-
plexity of O(log2 q). Further work by Couveignes [90, 91] and Lercier [217]
extended this so called SEA algorithm to work in small characteristic. A nice
introduction to these l-adic algorithms can be found in Chapter VII of the
¬rst volume [ECC].
At the end of 1999, Satoh [285] proposed a completely di¬erent strategy
based on p-adic methods. The main idea is to lift the curve and the Frobenius

endomorphism to a p-adic ring and to recover t modulo pm with pm > 4 q
directly from the lifted data. For ¬xed p, the time complexity of Satoh™s algo-
rithm is O(n2µ+1 ) and the space complexity is O(n3 ). Since the O-constant of
the time complexity grows as O(p2 logµ p), Satoh™s algorithm is only practical
for small p.
The purpose of this chapter is to explain the mathematical background of
Satoh™s algorithm and to present an overview of the more recent improvements
culminating in an algorithm by Harley that runs in O(n2µ log n) time using
O(n2 ) space for ¬xed p.
103
104 VI. POINT COUNTING

VI.1. p-adic Fields and Extensions
All p-adic point counting algorithms lift the Frobenius endomorphism to
a ring Zq whose reduction modulo p is isomorphic to Fq . In this section we
give a brief overview of the arithmetic in Zq . Further details can be found in
the books by Koblitz [201] and Serre [295].
Recall that the ¬eld of p-adic numbers Qp consists of power series

ai pi ,
±=
i=ν

with ν ∈ Z, 0 ¤ ai < p and aν = 0. By de¬nition, the valuation of ± is
ordp (±) = ν and the norm is |±|p = p’ν . The ring of p-adic integers or the
valuation ring of Qp is de¬ned as
Zp = {± ∈ Qp | ordp (±) ≥ 0} .
Note that for every m ∈ N we have Zp /(pm Zp ) ∼ Z/(pm Z), so Zp modulo p
=
simply is Fp . Every β ∈ Zp with ± ≡ β (mod p ) is called an approximation
m

of ± to precision m.
Let f (t) be a monic polynomial of degree n with coe¬cients in Zp and
assume that f (t) ≡ f (t) (mod p) is an irreducible polynomial over Fp . Note
that this implies that f (t) itself is irreducible over Qp . The algebraic extension
Qq = Qp (θ) with θ a root of f (t) is called an unrami¬ed extension of degree n
of Qp . Arithmetic in Qq thus reduces to polynomial arithmetic in Qp [t]/(f (t)).
n’1
i=0 ±i t with ±i ∈ Qp . Then the valuation of ± is de¬ned as
i
Let ± =
ordp (±) = mini ordp (±i ) and the norm is |±|p = p’ordp (±) . The valuation
ring Zq is de¬ned as Zp [t]/(f (t)) or equivalently Zq = {± ∈ Qq | ordp (±) ≥ 0}.
The Galois group Gal(Qq /Qp ) is isomorphic to Gal(Fq /Fp ). Indeed, every
automorphism Λ ∈ Gal(Qq /Qp ) induces an automorphism of Fq by reduction
modulo p. Since f (t) is square-free, this mapping is an isomorphism. The
Galois group Gal(Fq /Fp ) is cyclic and generated by the pth power Frobenius
automorphism
σ : Fq ’ Fq : x ’ x p .
The unique automorphism Σ ∈ Gal(Qq /Qp ) with Σ ≡ σ (mod p) is called the
Frobenius substitution on Qq . Note that, unlike σ, the Frobenius substitution
is not simply pth powering. Since Σ is an Zp -automorphism, i.e., is the
n’1
identity on Zp , we have Σ(±) = i=0 ±i Σ(t)i . The element Σ(t) ∈ Zq can
be computed using the Newton iteration xk+1 ← xk ’ f (xk )/f (xk ) starting
with x0 = tp .
Given a representation Fq ∼ Fp [t]/(f (t)), there are in¬nitely many poly-
=
nomials f (t) ∈ Zp [t] with f (t) ≡ f (t) (mod p). However, from an algorithmic
point of view, there are two lifts of f (t) that lead to e¬cient arithmetic. Note
that f (t) is normally chosen to be sparse, e.g. a trinomial or pentanomial in
characteristic 2, such that reduction modulo f (t) is very e¬cient.
VI.2. SATOH™S ALGORITHM 105

n
• Let f (t) = i=0 f i t with f i ∈ Fp for 0 ¤ i ¤ n. To preserve the
i

sparsity of f (t), a ¬rst natural choice is to de¬ne f (t) = n fi ti with
i=0
fi the unique integer between 0 and p’1 such that fi ≡ f i (mod p). The
reduction modulo f (t) of a polynomial of degree ¤ 2(n ’ 1) then only
takes n(w ’ 1) multiplications of a Zp -element by a small integer and
nw subtractions in Zp where w is the number of non-zero coe¬cients
of f (t).
• Since Fq is the splitting ¬eld of the polynomial tq ’ t, the polynomial
f (t) divides tq ’ t. To preserve the simple Galois structure of Fq , a
second natural choice is to de¬ne f (t) as the unique polynomial over
Zp with f (t)|tq ’ t and f (t) ≡ f (t) (mod p). Every root θ ∈ Zq of f (t)
clearly is a (q ’ 1)-th root of unity, therefore Σ(θ) is also a (q ’ 1)-th
root of unity. Since Σ(θ) ≡ θp (mod p), we conclude that Σ(θ) = θp or
by abuse of notation Σ(t) = tp .
VI.2. Satoh™s Algorithm
The basic idea of Satoh™s algorithm is to lift the curve E/Fq to a curve
E/Qq such that the Frobenius endomorphism F ∈ End(E) also lifts to an en-
domorphism F ∈ End(E). Since Tr(F) = Tr(F ), we can recover the number
of points as #E(Fq ) = q + 1 ’ Tr(F). Furthermore, E and F are de¬ned over
a ¬eld of characteristic zero, which allows us to compute Tr(F) modulo pm for
any precision m by analysing the action of F on an invariant di¬erential of E.
VI.2.1. The Canonical Lift of an Ordinary Elliptic Curve. Among
the many possible lifts of E from Fq to Qq , there is essentially only one that
admits a lift of the Frobenius endomorphism F .
Definition VI.1. The canonical lift E of an ordinary elliptic curve E over
Fq is an elliptic curve over Qq that satis¬es:
• the reduction modulo p of E equals E,
• End(E) ∼ End(E) as a ring.
=
Deuring [101] has shown that the canonical lift E always exists and is
unique up to isomorphism. Furthermore, a theorem by Lubin, Serre and
Tate [227] provides an e¬ective algorithm to compute the j-invariant of E
given the j-invariant of E.
Theorem VI.2 (Lubin-Serre-Tate). Let E be an ordinary elliptic curve over
Fq with j-invariant j(E) ∈ Fq \ Fp2 . Denote with Σ the Frobenius substitution
on Qq and with ¦p (X, Y ) the pth modular polynomial [ECC, pp. 50“55].
Then the system of equations
X ≡ j(E) (mod p),
¦p (X, Σ(X)) = 0 and (VI.1)
has a unique solution J ∈ Zq , which is the j-invariant of the canonical lift E
of E (de¬ned up to isomorphism).
106 VI. POINT COUNTING


The hypothesis j(E) ∈ Fp2 in Theorem VI.2 is necessary to ensure that
a certain partial derivative of ¦p does not vanish modulo p and guarantees
the uniqueness of the solution of equation (VI.1). The case j(E) ∈ Fp2 can
be handled very easily using the Weil conjectures [346]: since j(E) ∈ Fp2
there exists an elliptic curve E de¬ned over Fpe , with e = 1 or e = 2, that
is isomorphic to E over Fq . Let tk = pek + 1 ’ #E (Fpek ). Then tk+1 =
t1 tk ’ pe tk’1 with t0 = 2 and therefore #E(Fq ) = pn + 1 ’ tn/e . So in the
remainder of this chapter we will assume that j(E) ∈ Fp2 and in particular
that E is ordinary [307, Theorem V.3.1].
VI.2.2. Isogeny Cycles. Lifting the Frobenius endomorphism F directly
is not e¬cient since the degree of F is q. However, q = pn , so the Frobenius
endomorphism can be written as the composition of n isogenies of degree p.
σ
Let σ : E ’ E : (x, y) ’ (xp , y p ) be the pth power Frobenius isogeny, where
σ
E is the curve obtained by raising each coe¬cient of E to the pth power.
Repeatedly applying σ gives rise to the following cycle:
σ0 σ1 σ n’2 σ n’1
- E1 - ··· - E n’1 - E0 ,
E0
i
σ
with E i = E and σ i : E i ’ E i+1 : (x, y) ’ (xp , y p ). Composing these
isogenies, we can express the Frobenius endomorphism as
F = σ n’1 —¦ σ n’2 —¦ . . . —¦ σ 0 .
Instead of lifting E separately, Satoh lifts the whole cycle (E 0 , E 1 , . . . , E n’1 )
simultaneously leading to the diagram
Σ0 Σ1 Σn’2 Σn’1
- - - -
E0 E1 ··· En’1 E0
π π π π
(VI.2)
? ? ? ?
σ0 σ1 σ n’2 σ n’1
- - - -
···
E0 E1 E n’1 E0 ,

with Ei the canonical lift of E i and Σi the corresponding lift of σ i . The
existence of a lift of σ i is not trivial and follows from the following theorem
which can be found in Messing [246, Corollary 3.4].
Theorem VI.3. Let E 1 , E 2 be ordinary elliptic curves over Fq and E1 , E2
their respective canonical liftings. Then Hom(E 1 , E 2 ) ∼ Hom(E1 , E2 ).
=

VI.2.3. Computing the Canonical Lift. The theorem of Lubin, Serre
and Tate implies that the j-invariants of the Ei satisfy
¦p (j(Ei ), j(Ei+1 )) = 0 and j(Ei ) ≡ j(E i ) (mod p),
for i = 0, . . . , n ’ 1. De¬ne ˜ : Zn ’ Zn by
q q

˜(x0 , x1 , . . . , xn’1 ) = (¦p (x0 , x1 ), ¦p (x1 , x2 ), . . . , ¦p (xn’1 , x0 )).
VI.2. SATOH™S ALGORITHM 107

Then clearly we have ˜(j(En’1 ), j(En’2 ), . . . , j(E0 )) = (0, 0, . . . , 0). Using
a multivariate Newton iteration on ˜, we can lift the cycle of j-invariants
(j(E n’1 ), j(E n’2 ), . . . , j(E 0 )) to Zn with arbitrary precision. The iteration is
q
given by

(x0 , x1 , . . . , xn’1 ) ← (x0 , x1 , . . . , xn’1 ) ’ ((D˜)’1 ˜)(x0 , x1 , . . . , xn’1 ),

with (D˜)(x0 , . . . , xn’1 ) the Jacobian matrix
« 
···
¦p (x0 , x1 ) ¦p (x1 , x0 ) 0 0
¬ ·
¦p (x1 , x2 ) ¦p (x2 , x1 ) · · ·
0 0
¬ ·
¬ ·,
. . . . .
. . . . .
¬ ·
. . . . .
 · · · ¦p (xn’1 , xn’2 )
0 0 0
· · · ¦p (xn’1 , x0 )
¦p (x0 , xn’1 ) 0 0

where ¦p (X, Y ) denotes the partial derivative with respect to X. Note
that ¦p (Y, X) is the partial derivative of ¦p (X, Y ) with respect to Y since
¦p (X, Y ) is symmetric.
The pth modular polynomial satis¬es the Kronecker relation

¦p (X, Y ) ≡ (X p ’ Y )(X ’ Y p ) (mod p),

and since j(E i ) ∈ Fp2 and j(E i+1 ) = j(E i )p , we have
2
¦p (j(E i+1 ), j(E i )) ≡ j(E i )p ’ j(E i ) ≡ 0 (mod p),
¦p (j(E i ), j(E i+1 )) ≡ j(E i )p ’ j(E i )p ≡ 0 (mod p).

The above equations imply that (D˜)(x0 , . . . , xn’1 ) (mod p) is a diagonal
matrix with non-zero diagonal elements. Therefore, the Jacobian matrix is
invertible over Zq and thus δ = ((D˜)’1 ˜)(x0 , x1 , . . . , xn’1 ) ∈ Zn . Note that
q
we can simply apply Gauss elimination to solve

(D˜)(x0 , . . . , xn’1 )δ = ˜(x0 , . . . , xn’1 )

since the diagonal elements are all invertible. Using row operations we move
the bottom left element ¦p (x0 , xn’1 ) towards the right. After k row operations
this element becomes
k’1
¦p (xi+1 , xi )
k
(’1) ¦p (x0 , xn’1 ) ,
¦p (xi , xi+1 )
i=0

which clearly is divisible by pk since ¦p (xi+1 , xi ) ≡ 0 (mod p). This procedure
is summarized in Algorithm VI.1.
108 VI. POINT COUNTING




Algorithm VI.1: Lift j Invariants


Cycle ji ∈ Fq \ Fp2 with ¦p (ji , ji+1 ) ≡ 0 (mod p) for
INPUT:
0 ¤ i < n and precision m.
OUTPUT: Cycle Ji ∈ Zq with ¦p (Ji , Ji+1 ) ≡ 0 (mod pm ) and
Ji ≡ ji (mod p) for all 0 ¤ i < n.
1. If m = 1 then
For i = 0 to n ’ 1 do Ji ← ji .
2.
3. Else
m ← m , M ←m’m .
4. 2
(J0 , . . . , Jn’1 ) ← Lift j Invariants((j0 , . . . , jn’1 ), m ).
5.
For i = 0 to n ’ 2 do:
6.
t ← ¦p (Ji , Ji+1 )’1 (mod pM ).
7.
Di ← t¦p (Ji+1 , Ji ) (mod pM ).
8.
Pi ← t((¦p (Ji , Ji+1 ) (mod pm ))/pm ) (mod pM ).
9.
R ← ¦p (J0 , Jn’1 ) (mod pM ).
10.
S ← (((¦p (Jn’1 , J0 ) (mod pm )))/pm ) (mod pM ).
11.
For i = 0 to min(M, n ’ 2) do:
12.
S ← S ’ RPi (mod pM ).
13.
R ← ’ RDi (mod pM ).
14.
R ← R + ¦p (Jn’1 , J0 ) (mod pM ).
15.
Pn’1 ← SR’1 (mod pM ).
16.
For i = n ’ 2 to 0 by ’1 do Pi ← Pi ’ Di Pi+1 (mod pM ).
17.
For i = 0 to n ’ 1 do Ji ← Ji ’ pm Pi (mod pm ).
18.
19. Return (J0 , . . . , Jn’1 ).


As shown in Chapter III of the ¬rst volume [ECC], we can assume that
either E or its quadratic twist is given by an equation of the form
p = 2 : y 2 + xy = x3 + a, j(E) = 1/a,
j(E) = ’1/a,
p = 3 : y 2 = x3 + x2 + a,
p > 5 : y 2 = x3 + 3ax + 2a, j(E) = 1728a/(1 + a).
Once the j-invariant j(E) of the canonical lift of E is computed, a Weierstraß
model for E is given by
± = 1/(1728 ’ j(E)),
p = 2 : y 2 + xy = x3 + 36±x + ±,
± = 1/(1728 ’ j(E)),
p = 3 : y 2 = x3 + x2 /4 + 36±x + ±,
± = j(E)/(1728 ’ j(E)).
p > 5 : y 2 = x3 + 3±x + 2±,
Note that the above models have the correct j-invariant j(E) and reduce to
E modulo p.
VI.2. SATOH™S ALGORITHM 109

VI.2.4. The Trace of Frobenius. The canonical lift E of an ordinary el-
liptic curve E over Fq has the property that End(E) ∼ End(E). Let F be the
=
image of the Frobenius endomorphism F under this ring isomorphism; then
clearly Tr(F ) = Tr(F). Furthermore, since Qq has characteristic zero, the
exact value of Tr(F ) can be computed, and not just modulo p. The follow-
ing proposition gives an easy relation between the trace of an endomorphism
f ∈ End(E) and its action on an invariant di¬erential of E.
Proposition VI.4 (Satoh). Let E be an elliptic curve over Qq having good
reduction modulo p and let f ∈ End(E) of degree d. Let ω be an invariant
di¬erential on E and let f — (ω) = c ω be the action of f on ω. Then
d
Tr(f ) = c + .
c
Note that if we apply the above proposition to the lifted Frobenius endo-
morphism F, we get Tr(F) = b + q/b with F — (ω) = b ω. Since E is ordinary
it follows that either b or q/b is a unit in Zq . However, F is inseparable and
thus b ≡ 0 (mod p), which implies that b ≡ 0 (mod q), since q/b has to be
a unit in Zq . So if we want to compute Tr(F) (mod pm ), we would need
to determine b (mod pn+m ). Furthermore, it turns out to be quite di¬cult
to compute b directly. As will become clear later, we would need to know
Ker(Σi ), which is a subgroup of Ei [p] of order p. However, since Ker(σ i ) is
trivial we cannot use a simple lift of Ker(σ i ) to Ker(Σi ), but would need to
factor the p-division polynomial of Ei .
To avoid these problems, Satoh works with the Verschiebung V , i.e., the
dual isogeny of F , which is separable since E is ordinary and thus Ker(V ) can
be easily lifted to Ker(V), with V the image of V under the ring isomorphism
End(E) ∼ End(E). Furthermore, the trace of an endomorphism equals the
=
trace of its dual, so we have Tr(F) = Tr(V) = c + q/c with V — (ω) = c ω and c
a unit in Zq . Diagram (VI.2) shows that V = Σ0 —¦ Σ1 —¦ · · · —¦ Σn’1 and therefore
we can compute c from the action of Σi on an invariant di¬erential ωi of Ei
for i = 0, . . . , n ’ 1. More precisely, take ωi = Σi (ω) for 0 ¤ i < n and let ci
be de¬ned by
Σ— (ωi ) = ci ωi+1 .
i

Then c = 0¤i<n ci . Since V is separable, c will be non-zero modulo p and
we conclude
Tr(F ) ≡ ci (mod q) .
0¤i<n

Since all commutative squares in diagram (VI.2) are conjugates of each other,
we can also recover the trace of Frobenius as the norm of c0 , i.e.,
Tr(F ) ≡ NQq /Qp (c0 ) (mod q) .
110 VI. POINT COUNTING

VI.2.5. Computing the ci. The ¬nal step in Satoh™s algorithm is to com-
pute the coe¬cients ci using V´lu™s formulae [332], which need the equations
e
for Ei and Ei+1 and the kernel of Σi . Consider the following diagram:
Σi - Ei
Ei+1

3
Q

Q (VI.3)
νi QQ  »i
s
Ei+1 /Ker(Σi )

Given Ker(Σi ), Satoh uses V´lu™s formulae [332] to compute an equation for
e
the curve Ei /Ker(Σi ) and the isogeny νi . Since νi and Σi are both separa-
ble, Ker(νi ) = Ker(Σi ) and deg(νi ) = deg(Σi ), there exists an isomorphism
»i : Ei+1 /Ker(Σi ) ’ Ei that makes the above diagram commutative. Due to
V´lu™s construction, the action of νi on the invariant di¬erential is trivial,
e
i.e., νi— (ωi+1,K ) = ωi+1 with ωi+1,K the invariant di¬erential on Ei+1 /Ker(Σi ).
Therefore it is su¬cient to compute the action of »i on ωi .
Note that KerΣi is a subgroup of order p of Ei+1 [p]. Let Hi (x) be
(x ’ x(P )) ;
Hi (x) =
P ∈(KerΣi \{O})/±

then Hi (x) divides the p-division polynomial Ψp,i+1 (x) of Ei+1 . To ¬nd the
correct factor of Ψp,i+1 (x) Satoh proves the following lemma.
Lemma VI.5 (Satoh). Let p ≥ 3. Then KerΣi = Ei+1 [p] © Ei+1 (Zur ), with Zur
q q
the valuation ring of the maximal unrami¬ed extension Qur of Qq .
q
The above lemma implies that Hi (x) ∈ Zq [x] is the unique monic polyno-
mial of degree (p ’ 1)/2 that divides Ψp,i+1 (x) and such that Hi (x) (mod p) is
ˆ
square-free. Since E i is ordinary, Ker σ i = E i+1 [p] and Ψp,i+1 (x) (mod p) has
inseparable degree p. Therefore, δi Hi (x)p ≡ Ψp,i+1 (x) (mod p). This implies
that we cannot apply Hensel™s lemma since the polynomials Hi (x) (mod p)
and Ψp,i+1 (x)/Hi (x) (mod p) are not coprime. To this end, Satoh devized a
modi¬ed Hensel lifting [285, Lemma 2.1], which has quadratic convergence.
Lemma VI.6 (Satoh). Let p ≥ 3 be a prime and Ψ(x) ∈ Zq [x] satisfying
Ψ (x) ≡ 0 (mod p) and Ψ (x) ≡ 0 (mod p2 ). Let h(x) ∈ Zq [x] be a monic
polynomial such that
1. h(x) (mod p) is square-free and coprime to (Ψ (x)/p) (mod p),
2. Ψ(x) ≡ q(x)h(x) (mod pm+1 ).
Then the polynomial
Ψ(x)
H(x) = h(x) + h (x) (mod h(x))
Ψ (x)
satis¬es H(x) ≡ h(x) (mod pm ) and Ψ(x) ≡ Q(x)H(x) (mod p2m+1 ).
VI.2. SATOH™S ALGORITHM 111




Algorithm VI.2: Lift Kernel

The p-division polynomial Ψp (x) of an elliptic curve E
INPUT:
over Zq /(pm Zq ), precision m.
OUTPUT: H(x) = P ∈(KerΣi \{O})/± (x ’ x(P )) (mod pm’1 ).
If m = 1 then
1.
H(x) ← h(x) monic with Ψp (x) ≡ δh(x)p (mod p).
2.
3. Else
m ← m’1 .
4. 2
H(x) ← Lift Kernel(Ψp (x), m ).
5.
H(x) ← H(x) + H (x)Ψp (x) (mod H(x)) (mod pm ).
6. Ψp (x)
Return H(x).
7.

For p > 3, Ei+1 can be de¬ned by the equation y 2 = x3 + Ai+1 x + Bi+1 .
Using V´lu™s formulae, Satoh [285, Proposition 4.3] shows that Ei+1 /Ker(Σi )
e
is given by the equation y 2 = x3 + ±i+1 x + βi+1 with
±i+1 = (6 ’ 5p)Ai+1 ’ 30(h2 ’ 2hi,2 ),
i,1

βi+1 = (15 ’ 14p)Bi+1 ’ 70(’h3 + 3hi,1 hi,2 ’ 3hi,3 ) + 42Ai+1 hi,1 ,
i,1

where hi,k denotes the coe¬cient of x(p’1)/2’k in Hi (x) and we de¬ne hi,k = 0
for (p ’ 1)/2 ’ k < 0.
Given the above Weierstraß model for Ei+1 /Ker(Σi ) we can now compute
the isomorphism »i to Ei : y 2 = x3 + Ai x + Bi . The only change of variables
preserving the form of these equations is »i : (x, y) ’ (u2 x, u3 y) with
i i

±i+1 Bi
u2 = .
i
βi+1 Ai
The action of »i on ωi is given by »— (ωi ) = u’1 ωi+1,K , and therefore
i i

βi+1 Ai
c2 = . (VI.4)
i
±i+1 Bi
n’1
Computing c2 = i=0 c2 = NQq /Qp (c2 ) and taking the square root gives the
i 0
trace of Frobenius up to the sign. As shown in the proof of [307, Theorem
V.4.1], we have
n’1
t ≡ γγ σ · · · γ σ (mod p),
where γ is the coe¬cient of xp’1 in the polynomial (x3 + 3ax + 2a)(p’1)/2 .
This ¬nally leads to Algorithm VI.3.
112 VI. POINT COUNTING



Algorithm VI.3: Satoh

INPUT: Elliptic curve E : y 2 = x3 + ax + b over Fpn , j(E) ∈ Fp2 .
OUTPUT: The number of points on E(Fpn ).
1. m ← logp 4 + n/2 .
2. S ← 1, T ← 1.
3. j0 ← jn ← j(E).
4. For i = 0 to n ’ 2 do:
ji+1 ← jip .
5.
6. (Jn’1 , . . . , J0 ) ← Lift j Invariants((jn’1 , . . . , j0 ), m).
7. For i = 0 to n ’ 1 do:
γ ← Ji /(1728 ’ Ji ) (mod pm ).
8.
A ← 3γ (mod pm ), B ← 2γ (mod pm ).
9.
Ψp (x) ← p-division polynomial of y 2 = x3 + Ax + B.
10.
H(x) ← Lift Kernel(Ψp (x), m + 1).
11.
For j = 1 to 3 do:
12.
hj ← Coeff(H(x), (p ’ 1)/2 ’ j).
13.
± ← (6 ’ 5p)A ’ 30(h2 ’ 2h2 ).
14. 1
β ← (15 ’ 14p)B ’ 70(’h3 + 3h1 h2 ’ 3h3 ) + 42Ah1 .
15. 1
S ← βAS, T ← ±BT .
16.
17. t ← Sqrt(S/T, m).
18. γ ← Coeff((x3 + ax + b)(p’1)/2 , p ’ 1).
n’1
19. If t ≡ γγ σ · · · γ σ (mod p) then t ← ’ t (mod pm ).
20. If t2 > 4pn then t ← t ’ pm .
21. Return pn + 1 ’ t.

The case p = 3 is very similar to the case p ≥ 5. There are only two minor
adaptations: ¬rstly, note that Ker Σi = {Q, ’Q, O} with Q a 3-torsion point
on Ei+1 with integral coordinates, so Algorithm VI.2 reduces to a simple New-
ton iteration on the 3-division polynomial of Ei+1 ; secondly, the Weierstraß
equation for Ei is di¬erent from the one for p ≥ 5, which slightly changes
V´lu™s formulae. Let xQ denote the x-coordinate of Q ∈ Ker Σi and let Ei+1
e
be de¬ned by y 2 = x3 + x2 /4 + Ai+1 x + Bi+1 . Then Ei+1 /Ker(Σi ) is given by
the equation y 2 = x3 + x2 /4 + ±i+1 x + βi+1 , with
±i+1 = ’15x2 ’ (5/2)xQ ’ 4Ai+1 ,
Q

βi+1 = ’49x3 ’ (27/2)x2 ’ (35Ai+1 + 1/2)xQ ’ Ai+1 ’ 27Bi+1 .
Q Q

Analogous to the case p ≥ 5, we conclude that c2 is given by (VI.4) and
i
n’1 2
2
taking the square root of c = i=0 ci determines the trace of Frobenius t up
to the sign. Furthermore, since the curve E is de¬ned by an equation of the
form y 2 = x3 + x2 + a, the correct sign follows from t ≡ 1 (mod 3).
VI.2. SATOH™S ALGORITHM 113

For p = 2, Lemma VI.5 no longer holds. Indeed, the Newton polygon
of the 2-division polynomial shows that there are two non-trivial points in
Ei+1 [p] © Ei+1 (Zur ), whereas Ker Σi has only one non-trivial point. The main
q
problem in extending Satoh™s algorithm to characteristic 2 therefore lies in
choosing the correct 2-torsion point. There are two algorithms which are both
based on diagram (VI.3). Let Ker Σ = Q ; then, since » is an isomorphism,
we conclude j(Ei+1 / Q ) = j(Ei ).
The ¬rst algorithm to compute Q is due to Skjernaa [308] who gives an
explicit formula for the x-coordinate xQ as a function of j(Ei ) and j(Ei+1 ).
Since Q is a 2-torsion point, it follows that 2yQ + xQ = 0. Substituting yQ in
the equation of the curve and using the equality j(Ei+1 / Q ) = j(Ei ), Skjernaa
deduces an explicit expression for xQ . A proof of the following proposition
can be found in [308, Lemma 4.1].

Proposition VI.7. Let Q = (xQ , yQ ) be the non-trivial point in Ker Σi+1
and let zQ = xQ /2. Then
2
j(E ) +195120j(Ei )+4095j(Ei+1 )+660960000
zQ = ’ 8(j(Ei )2 +j(Eii)(563760’512j(Ei+1 ))+372735j(Ei+1 )+8981280000) .

Skjernaa shows that the 2-adic valuation of both the numerator and the
denominator is 12, so we have to compute j(Ei ) (mod 2m+12 ) to recover
zQ (mod 2m ).
The second algorithm is due to Fouquet, Gaudry and Harley [123] and
is based on the fact that Ker Σi = Q ‚ Ei+1 [2]. Let Ei+1 be given by the
equation y 2 + xy = x3 + 36Ai+1 x + Ai+1 with Ai+1 = 1/(1728 ’ j(Ei+1 )). Since
Q is a 2-torsion point, we have 2yQ +xQ = 0 and the x-coordinate xQ is a zero
of the 2-division polynomial 4x3 + x2 + 144Ai+1 x + 4Ai+1 . Clearly we have
xQ ≡ 0 (mod 2), so Fouquet, Gaudry and Harley compute zQ = xQ /2 as a
zero of the modi¬ed 2-division polynomial 8z 3 +z 2 +72Ai+1 z+Ai+1 . The main
problem is choosing the correct starting value when considering this equation
modulo 8. Using j(Ei+1 / Q ) = j(Ei ) they proved that z ≡ 1/j(Ei ) (mod 8)
is the correct starting value giving xQ .
V´lu™s formulae show that Ei+1 /Ker Σi is given by the Weierstraß equation
e
y + xy = x3 + ±i+1 x + βi+1 with
2


36
±i+1 = ’ ’ 5γi+1 ,
j(Ei+1 ) ’ 1728
1
=’ ’ (1 + 7xQ )γi+1 ,
βi+1
j(Ei+1 ) ’ 1728

where γi+1 = 3x2 ’ 36/(j(Ei+1 ) ’ 1728) + xQ /2. The isomorphism »i now has
Q
the general form

(ui , ri , si , ti ) ∈ Q— — Q3 ,
(x, y) ’ (u2 x + ri , u3 y + u2 si x + ti ),
i i i q q
114 VI. POINT COUNTING

but an easy calculation shows that c2 = u’2 . Solving the equations satis¬ed
i i
by (ui , ri , si , ti ) given in [307, Table 1.2] ¬nally leads to
864βi ’ 72±i + 1
c2 = ’ . (VI.5)
48±i ’ 1
i


The complexity of Algorithm VI.3 directly follows from Hasse™s theorem,

which states that |t| ¤ 2 q. Therefore it su¬ces to lift all data with precision
n/2. Since elements of Zq /(pm Zq ) are represented as polynomials of
m
degree less than n with coe¬cients in Z/(pm Z), every element takes O(n2 )
memory for ¬xed p. Therefore, multiplication and division in Zq /(pm Zq ) take
O(n2µ ) time.
For each curve E i with 0 ¤ i < n we need O(1) elements of Zq /(pm Zq ),
so the total memory needed is O(n3 ) bits. Lifting the cycle of j-invariants to
precision m requires O(log m) iterations. In every iteration the precision of
the computations almost doubles, so the complexity is determined by the last
iteration, which takes O(n2µ+1 ) bit-operations. Computing one coe¬cient
c2 requires O(1) multiplications, so to compute all ci we also need O(n2µ+1 )
i
bit-operations.
In conclusion, there exists a deterministic algorithm to compute the num-
ber of points on an elliptic curve E over a ¬nite ¬eld Fq with q = pn and
j(E) ∈ Fp2 , which requires O(n2µ+1 ) bit-operations and O(n3 ) space for
¬xed p.

VI.2.6. Vercauteren™s Algorithm. The ¬rst improvement of Satoh™s
algorithm and its extensions to characteristics 2 and 3 is an algorithm by
Vercauteren [334] that only requires O(n2 ) space but still runs in O(n2µ+1 )
time. The basic idea is very simple: the trace of Frobenius t can be com-
puted as t ≡ 0¤i<n ci (mod q) and the ci only depend on the curves Ei and
Ei+1 . So the main problem of Satoh™s algorithm is that it lifts all j-invariants
simultaneously, instead of lifting one j-invariant at a time.
Let Ji ≡ j(Ei ) (mod pm ). Then Ji+1 ≡ j(Ei+1 ) (mod pm ) can be computed
using a univariate Newton iteration on ¦p (X, Ji ). This iteration is given by

¦p (Z, Ji )
Z←Z’ , (VI.6)
‚¦p
(Z, Ji )
‚X

starting from j(E i+1 ) ≡ j(Ei+1 ) (mod p) as an initial approximation. Note
that since ¦p (X, Y ) satis¬es the Kronecker relation, ‚¦p (Ji+1 , Ji ) will be a
‚X
unit in Zq . The following proposition shows that the iteration (VI.6) has a
quite remarkable property: let Ji+1 be the zero of ¦p (X, Ji ); then Ji+1 equals
j(Ei+1 ) up to precision m + 1 and not just up to precision m as one would
expect.
VI.3. ARITHMETIC GEOMETRIC MEAN 115

Proposition VI.8. Let Qq be an unrami¬ed extension of Qp and denote with
Zq its valuation ring. Let g ∈ Zq [X, Y ] and assume that x0 , y0 ∈ Zq satisfy
‚g ‚g
g(x0 , y0 ) ≡ 0 (mod p), (x0 , y0 ) ≡ 0 (mod p), (x0 , y0 ) ≡ 0 (mod p).
‚X ‚Y
Then the following properties hold:
1. For every y ∈ Zq with y ≡ y0 (mod p) there exists a unique x ∈ Zq
such that x ≡ x0 (mod p) and g(x, y) = 0.
2. Let y ∈ Zq with y ≡ y (mod pm ), m ≥ 1 and let x ∈ Zq be the unique
element with x ≡ x0 (mod p) and g(x , y ) = 0. Then x satis¬es
x ≡ x (mod pm+1 ).
Repeatedly applying this proposition immediately leads to the following
algorithm:

Algorithm VI.4: Lift First j Invariant

INPUT: A j-invariant j ∈ Fpn \ Fp2 and a precision m.
m’1
OUTPUT: J ∈ Zq with J ≡ j p (mod p) and ¦p (J, Σ(J)) ≡ 0 (mod pm ).
1. J ← j (mod p).
2. For i = 2 to m do:
J ← Newton Iteration(¦p (X, J), J p (mod p), i).
3.
4. Return J.

To obtain an O(n2 ) space algorithm, we simply interleave the lifting of
the j-invariants with the computation of c in Step 5 of Algorithm VI.3.
Note that the convergence of Algorithm VI.4 is only linear, i.e., for every
iteration of the For-loop, the precision increases by one. However, once we
have computed one j-invariant with su¬cient precision, we can switch to the
Newton iteration (VI.6), which converges quadratically.
In conclusion, there exists a deterministic algorithm to compute the num-
ber of points on an elliptic curve E over a ¬nite ¬eld Fq with q = pn and
j(E) ∈ Fp2 , which requires O(n2µ+1 ) bit-operations and O(n2 ) space for
¬xed p.

VI.3. Arithmetic Geometric Mean
In a letter to Gaudry and Harley, Mestre [247] described a very elegant
algorithm based on the Arithmetic Geometric Mean (AGM) to count the
number of points on ordinary curves of genus 1 and 2 over F2n . Carls [60] and
Kohel [208] showed how to extend this algorithm to higher characteristics. In
this section we give a detailed description of both the bivariate and univariate
versions of the AGM. Note that the AGM algorithm for elliptic curves is
protected by a U.S. patent [160] ¬led by Harley and Mestre.
116 VI. POINT COUNTING

For a0 , b0 ∈ R with a0 ≥ b0 > 0, de¬ne the AGM iteration for k ∈ N as
ak + bk
(ak+1 , bk+1 ) = , ak bk .
2
Then bk ¤ bk+1 ¤ ak+1 ¤ ak and 0 ¤ ak+1 ’ bk+1 ¤ (ak ’ bk )/2; therefore
limk’∞ ak = limk’∞ bk exists. This common value is called the AGM of a0
and b0 and is denoted by AGM(a0 , b0 ). An easy calculation shows that
a0 ’ b0
ak 1 a0
’1¤ k ¤k ’1 ,
bk 2 bk 2 b0
so after a logarithmic number √ steps we have ak /bk = 1+µk with µk < 1. The
of
Taylor series expansion of 1/ 1 + µk shows that convergence even becomes
quadratic:
µ2 µ3 15µ4 7µ5
ak+1 ak + bk 2 + µk
=√ =√ =1+ k ’ k + ’ k + O(µ6 ) . (VI.7)
k
k
bk+1 8 8 128 64
2 1 + µk
2 ak bk
VI.3.1. The AGM Isogeny and the Canonical Lift. Let Qq be a de-
gree n unrami¬ed extension of Q2 with valuation ring Zq and residue ¬eld Fq .

Denote by c for c ∈ 1 + 8Zq the unique element d ∈ 1 + 4Zq with d2 = c.
For elements a, b ∈ Zq with a/b ∈ 1 + 8Zq , a = (a + b)/2 and b = b a/b
also belong to Zq and a /b ∈ 1 + 8Zq . Furthermore, if a, b ∈ 1 + 4Zq , then
also a , b ∈ 1 + 4Zq . However, as can be seen from equation (VI.7), the AGM
sequence will converge if and only if a/b ∈ 1 + 16Zq . For a/b ∈ 1 + 8Zq , the
AGM sequence will not converge at all.
Let a, b ∈ 1 + 4Zq with a/b ∈ 1 + 8Zq and Ea,b the elliptic curve de¬ned
by y 2 = x(x ’ a2 )(x ’ b2 ). Note that Ea,b is not a minimal Weierstraß model
and that its reduction modulo 2 is singular. The following lemma gives an
isomorphism from Ea,b to a minimal model.
Lemma VI.9. Let a, b ∈ 1 + 4Zq with a/b ∈ 1 + 8Zq and Ea,b the elliptic curve
de¬ned by y 2 = x(x ’ a2 )(x ’ b2 ). Then the isomorphism
x ’ ab y ’ x + ab
(x, y) ’ ( , )
4 8
in y 2 + xy = x3 + rx2 + sx + t with
transforms Ea,b
± 2 2
 r = ’a +3ab’b ’1 ,
42 2
3 3
s = ’a b+2a b ’ab , (VI.8)
 83 3 2 4
42
t = ’a b +2a b ’a b .
64
a’b 2
Furthermore, r ∈ 2Zq , s ∈ 8Zq , t ≡ ’ (mod 16) and the equation
8
de¬nes a minimal Weierstraß model.
The next proposition shows that the AGM iteration constructs a sequence
of elliptic curves all of which are 2-isogenous. This will provide the missing
link between the AGM iteration and the canonical lift.
VI.3. ARITHMETIC GEOMETRIC MEAN 117

Proposition VI.10. Let a, b ∈ 1 + 4Zq with a/b ∈ 1 + 8Zq and Ea,b the
elliptic curve de¬ned by the equation y 2 = x(x’a2 )(x’b2 ). Let a = (a+b)/2,

b = ab and Ea ,b : y 2 = x(x ’ a 2 )(x ’ b 2 ). Then Ea,b and Ea ,b are 2-
isogenous. The isogeny is given by
(x + ab)2 (x ’ ab)(x + ab)
φ : Ea,b ’ Ea ,b : (x, y) ’ ,y ,
8x2
4x
and the kernel of φ is (0, 0) . Furthermore, the action of φ on the invariant
di¬erential dx/y is
dx dx
φ— =2 .
y y
Let E be an ordinary elliptic curve de¬ned by y 2 + xy = x3 + c with c ∈ F— q
and let E be its canonical lift. Take any r ∈ Zq such that r2 ≡ c (mod 2)
and let a0 = 1 + 4r and b0 = 1 ’ 4r. Then Lemma VI.9 shows that Ea0 ,b0 is
isomorphic to a lift of E to Zq and thus j(Ea0 ,b0 ) ≡ j(E) (mod 2).
Let (ak , bk )∞ be the AGM sequence and consider the elliptic curves
k=0
Eak ,bk . Proposition VI.10 implies that ¦2 j(Eak+1 ,bk+1 ), j(Eak ,bk ) = 0 and
an easy computation shows that j(Eak+1 ,bk+1 ) ≡ j(Eak ,bk )2 (mod 2). Note
that ¦2 (X, Y ) and (j(Eak+1 ,bk+1 ), j(Eak ,bk )) satisfy the conditions of Proposi-
tion VI.8, so we conclude
j (Eak ,bk ) ≡ Σk (j(E)) (mod 2k+1 ) .
Although the AGM sequence (ak , bk )∞ itself does not converge, the sequence
k=0
of elliptic curves (Eank ,bnk )∞ does converge since limk’∞ j(Eank ,bnk ) exists
k=0
and is equal to the j-invariant of the canonical lift of E.

VI.3.2. Computing the Trace of Frobenius. The AGM not only pro-
vides an e¬cient algorithm to compute the j-invariant of the canonical lift E,
but it also leads to an elegant formula for the trace of Frobenius.
Assume we have computed a, b ∈ 1 + 4Zq with a/b ∈ 1 + 8Zq such that

j(Ea,b ) = j(E). Let (a , b ) = ((a + b)/2, ab), φ : Ea,b ’ Ea ,b the AGM
isogeny and Σ : Ea,b ’ EΣ(a),Σ(b) the lift of the 2nd-power Frobenius. Then
we have the following diagram:

φ - Ea ,b
Ea,b
Q 
Q  (VI.9)
Σ QQ  »
s+
EΣ(a),Σ(b)

The kernel of the Frobenius isogeny Σ : Ea,b ’ EΣ(a),Σ(b) is a subgroup of
order 2 of
Ea,b [2] = {O, (0, 0), (a2 , 0), (b2 , 0)} .
118 VI. POINT COUNTING

The isomorphism given in Lemma VI.9 allows us to analyse the reduction of
the 2-torsion on a minimal model. An easy calculation shows that (0, 0) is
mapped onto O whereas (a2 , 0) and (b2 , 0) are mapped to (0, (a’b)/8 (mod 2)).
Therefore we conclude that Ker Σ = {O, (0, 0)}. Proposition VI.10 shows that
Ker Σ = Ker φ, and, since both isogenies are separable, there exists an isomor-
phism » : Ea ,b ’ EΣ(a),Σ(b) such that Σ = » —¦ φ. The following proposition
shows that this isomorphism has a very simple form.
Proposition VI.11. Given two elliptic curves Ea,b : y 2 = x(x ’ a2 )(x ’ b2 )
and Ec,d : y 2 = x (x ’ c2 )(x ’ d2 ) over Qq with a, b, c, d ∈ 1 + 4Zq and
a/b, c/d ∈ 1 + 8Zq , then Ea,b and Ec,d are isomorphic if and only if x = u2 x
c2 2 2
2 c2 2
and y = u3 y with u2 = a2+d2 . Furthermore, a = d or a = d .
+b b b c

Let ω = dx/y and ω = dx /y be invariant di¬erentials on Ea,b and
EΣ(a),Σ(b) , respectively. Then
Σ— (ω ) = (» —¦ φ)— (ω ) = 2u’1 ω ,
2 2
with u2 = Σ(a)2 +Σ(b) . De¬ne ζ = a/b = 1 + 8c and ζ = a /b = 1 + 8c . Then
a +b 2
Proposition VI.11 also implies that
1
ζ 2 = Σ(ζ)2 or ζ 2 = .
Σ(ζ)2
Substituting ζ = 1 + 8c and ζ = 1 + 8c in the above equation and dividing
by 16, we conclude that c ≡ Σ(c) (mod 4) or c ≡ ’Σ(c) (mod 4). The Taylor

expansion of 1+8c = (1+4c)/ 1 + 8c modulo 32 shows that c ≡ c2 (mod 4).
Since after the ¬rst iteration c itself is a square ±2 modulo 4, and since
Σ(±2 ) ≡ ±4 (mod 4), we conclude that ζ 2 = Σ(ζ)2 . Note that this implies
a a
ζ=
= Σ(ζ) = Σ( ) , (VI.10)
b b
since ζ ≡ ζ ≡ 1 (mod 8). Substituting b 2 = a 2 Σ(b)/Σ(a)2 in the expression
for u2 and taking square roots leads to
Σ(a)
u=± .
a
Let (ak , bk )∞ be the AGM sequence with a0 = a and b0 = b and consider
k=0
the following diagram where Ek = EΣk (a),Σk (b) and Σk : Ek ’ Ek+1 the lift of
the 2nd-power Frobenius isogeny.
φ0 φ1 φ2 φn’1
- - - -
···
Ea,b Ea1 ,b1 Ea2 ,b2 Ean ,bn
.
.
Id »1 »2 »n
.
? ? ? ?
Σ0 Σ1 Σ2 Σn’1
- - - -
E0 E1 E2 ··· En = E0
Since Ker Σk —¦ »k = Ker φk for k ∈ N, we can repeat the same argument
as for diagram (VI.9) and ¬nd an isomorphism »k+1 such that the square
VI.3. ARITHMETIC GEOMETRIC MEAN 119

commutes, i.e., Σk = »k+1 —¦ φk —¦ »’1 . Since Ea,b is isomorphic to the canonical
k
lift E of E, we conclude that

Tr(Σn’1 —¦ · · · —¦ Σ0 ) = Tr F = Tr F .

The above diagram shows that Σn’1 —¦ · · · —¦ Σ0 = »n —¦ φn’1 —¦ · · · —¦ φ0 and,
since φk acts on the invariant di¬erential ω as multiplication by 2 and »n as
multiplication by ±an /a0 , we conclude that
an
F — (ω) = ±2n (ω) .
a0
The Weil conjectures imply that the product of the roots of the characteristic
polynomial of Frobenius is 2n and thus
a0 an
Tr F = Tr F = ± ± 2n . (VI.11)
an a0
Equation (VI.10) implies that ak+1 /ak+2 = Σ(ak /ak+1 ), which leads to
a0 a0 a1 an’1 a0
···
= = NQq /Qp ( ) .
an a1 a2 an a1

If the curve E is de¬ned by the equation y 2 + xy = x3 + c with c ∈ F— ,
√√ q
then ( c, c) is a point of order 4, which implies that TrF ≡ 1 (mod 4).
4


Since a0 /an ∈ 1 + 4Zq , we can choose the correct sign in equation (VI.11) and
conclude that TrF ≡ a0 /an ≡ NQq /Qp ( a1 ) (mod q).
a0




VI.3.3. The AGM Algorithm. The only remaining problem is that we
only have approximations to a and b and not the exact values as assumed in
the previous section.
Let E be an ordinary elliptic curve de¬ned by y 2 +xy = x3 +c with c ∈ F— .
q
Take any r ∈ Zq such that r ≡ c (mod 2) and let a0 = 1 + 4r and b0 = 1 ’ 4r.
2

<<

. 4
( 10)



>>