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