Algorithm 3.62 for computing ρ = k mod δ is cumbersome to implement on some platforms because it requires two multiprecision integer divisions (in step 4). Algorithm 3.65 computes an element ρ ≡ k (mod δ) without the expensive multiprecision integer divisions. We write ρ = k partmod δ. Solinas proved that l(ρ) ≤ m + a and if C ≥ 2 then l(ρ ) ≤ m + a + 3. However, it is still possible that l(ρ ) is significantly bigger than l(ρ). This is not a concern in practice since the probability that ρ = ρ is less than 2−(C−5)—hence selection of a sufficiently large C ensures ρ = ρ with overwhelming probability.

Algorithm 3.65 Partial reduction modulo δ = (τ m − 1)/(τ − 1)

INPUT: k [1, n − 1], C ≥ 2, s0 = d0 + µd1, s1 = −d1, where δ = d0 + d1τ . OUTPUT: ρ = k partmod δ.

1.k ← k/2a−C+(m−9)/2 .

2.Vm ← 2m + 1 − #Ea (F2m ).

3.For i from 0 to 1 do

3.1g ← si · k . j ← Vm · g /2m .

3.2λi ← (g + j )/2(m+5)/2 + 12 /2C .

4.Use Algorithm 3.63 to compute (q0, q1) ← Round(λ0, λ1).

5.r0 ← k − (s0 + µs1)q0 − 2s1q1, r1 ← s1q0 − s0q1.

6.Return(r0 + r1τ ).

3.4.2Point multiplication

Algorithm 3.66 is an efficient point multiplication method that incorporates the ideas of the preceding subsection. Since the length of TNAF(ρ ) is approximately m, and since its density is expected to be about 1/3, Algorithm 3.66 has an expected running time of approximately

120 3. Elliptic Curve Arithmetic

Window methods

If some extra memory is available, the running time of Algorithm 3.66 can be decreased by deploying a window method which processes w digits of ρ at a time. This is achieved by using a width-w TNAF, which can be viewed as a τ -adic analogue of the ordinary width-w NAF (Definition 3.32).

Theorem 3.67 Let {Uk } be the integer sequence defined by U0 = 0, U1 = 1, Uk+1 = µUk − 2Uk−1 for k ≥ 1.

(i)Uk2 − µUk−1Uk + 2Uk2−1 = 2k−1 for all k ≥ 1.

(ii)Let tk = 2Uk−1Uk−1 mod 2k for k ≥ 1. (Since Uk is odd for each k ≥ 1, Uk−1 mod

2k does indeed exist.) Then tk2 + 2 ≡ µtk (mod 2k ) for all k ≥ 1.

From (3.32) and Theorem 3.67(ii), it follows that the map φw : Z[τ ] → Z2w induced by τ → tw is a surjective ring homomorphism with kernel {α Z[τ ] : τ w divides α}.

Moreover, a set of distinct representatives of the equivalence classes of Z[τ ] modulo τ w is {0, ±1, ±2, ±3, . . . , ±(2w−1 − 1), −2w−1}, of which {±1, ±3, . . . , ±(2w−1 − 1)}

are not divisible by τ .

Note that TNAF2(κ ) = TNAF(κ ). Tables 3.9 and 3.10 list the αu ’s for a {0, 1} and 3 ≤ w ≤ 6. The expressions given for each αu has at most two terms that involve

the TNAF; a few exceptions were made where use of the TNAF is less efficient. With these expressions, each αu P can be computed using at most one elliptic curve addition operation.

TNAFw (ρ) can be efficiently computed using Algorithm 3.69. In Algorithm 3.69, k mods 2w denotes the integer u satisfying u ≡ k (mod 2w ) and −2w−1 ≤ u < 2w−1. The digits of TNAFw (ρ) are obtained by repeatedly dividing ρ by τ , allowing remainders γ in {0, ±α1, ±α3 . . . , ±α2w−1−1}. If ρ is not divisible by τ and the remainder chosen is αu where u = φw (ρ) mods 2w , then (ρ − αu )/τ will be divisible by τ w−1, ensuring that the next w − 1 digits are 0.

124 3. Elliptic Curve Arithmetic

does not yield a speedup that is as dramatic as achieved in §3.4 for Koblitz curves (where all the point doublings are replaced by much faster applications of the Frobenius map), it can be used to accelerate point multiplication on a larger class of curves including some elliptic curves over large prime fields. Roughly speaking, if the endomorphism can be computed in no more time than it takes to perform a small number of point doublings, then the technique eliminates about half of all doublings and reduces the point multiplication time by roughly 33%.

Endomorphisms of elliptic curves

Let E be an elliptic curve defined over a field K . The set of all points on E whose coordinates lie in any finite extension of K is also denoted by E. An endomorphism φ of E over K is a map φ : E → E such that φ (∞) = ∞ and φ ( P) = (g( P), h( P)) for all P E, where g and h are rational functions whose coefficients lie in K . The set of all endomorphisms of E over K forms a ring, called the endomorphism ring of E over K . An endomorphism φ is also a group homomorphism, that is,

φ ( P1 + P2) = φ ( P1) + φ ( P2) for all P1, P2 E.

The characteristic polynomial of an endomorphism φ is the monic polynomial f (X) of least degree in Z[X] such that f (φ) = 0, that is, f (φ)( P) = ∞ for all P E. If E is a non-supersingular elliptic curve, then the characteristic polynomial of φ has degree 1 or 2.

Example 3.71 (endomorphisms of elliptic curves)

(i)Let E be an elliptic curve defined over Fq . For each integer m, the multiplication by m map [m] : E → E defined by

[m] : P → m P

is an endomorphism of E defined over Fq . A special case is the negation map defined by P → − P. The characteristic polynomial of [m] is X − m.

(ii)Let E be an elliptic curve defined over Fq . Then the q-th power map φ : E → E defined by

φ : (x, y) → (xq , yq ), φ : ∞ → ∞

is an endomorphism of E defined over Fq , called the Frobenius endomorphism. The characteristic polynomial of φ is X2 − t X + q, where t = q + 1 − #E(Fq ).

(iii) Let p ≡ 1 (mod 4) be a prime, and consider the elliptic curve

E : y2 = x3 + ax

defined over F p. Let i F p be an element of order 4. Then the map φ : E → E

defined by

φ : (x, y) → (−x, i y), φ : ∞ → ∞

is an endomorphism of E defined over F p. Note that φ ( P) can be computed using only one multiplication. The characteristic polynomial of φ is X2 + 1.

(iv) Let p ≡ 1 (mod 3) be a prime, and consider the elliptic curve

E : y2 = x3 + b

defined over F p. Let β F p be an element of order 3. Then the map φ : E → E defined by

φ : (x, y) → (β x, y), φ : ∞ → ∞

is an endomorphism of E defined over F p. Note that φ ( P) can be computed using only one multiplication. The characteristic polynomial of φ is X2 + X + 1.

Note 3.72 (integer representation of an endomorphism) Suppose now that E is an elliptic curve defined over the finite field Fq . Suppose also that #E(Fq ) is divisible by a prime n, and that n2 does not divide #E(Fq ). Then E(Fq ) contains exactly one subgroup of order n; let this subgroup be P where P E(Fq ) has order n. If φ is an endomorphism of E defined over Fq , then φ ( P) E(Fq ) and hence φ ( P) P . Suppose that φ ( P) = ∞. Then we can write

φ ( P) = λ P for some λ [1, n − 1].

In fact λ is a root modulo n of the characteristic polynomial of φ.

Example 3.73 (the elliptic curve P-160) Consider the elliptic curve

E : y2 = x3 + 3

defined over the 160-bit prime field F p, where

p= 2160 − 229233

= 1461501637330902918203684832716283019655932313743.

Since p ≡ 1 (mod 3), the curve is of the type described in Example 3.71(iv). The group of F p-rational points on E has prime order

#E(F p ) = n = 1461501637330902918203687013445034429194588307251.

An element of order 3 in F p is

β = 771473166210819779552257112796337671037538143582

and so the map φ : E → E defined by φ : ∞ → ∞ and φ : (x, y) → (β x, y) is an endomorphism of E defined over F p. The solution

λ = 903860042511079968555273866340564498116022318806

to the equation λ2 + λ + 1 ≡ 0 (mod n) has the property that φ ( P) = λ P for all P E(F p).

126 3. Elliptic Curve Arithmetic

Accelerating point multiplication

The strategy for computing k P, where k [0, n − 1], is the following. First write

where the integers k1 and k2 are of approximately half the bitlength of k. Such an expression is called a balanced length-two representation of k. Since

k P can be obtained by first computing φ ( P) and then using simultaneous multiple point multiplication (Algorithm 3.48) or interleaving (Algorithm 3.51) to evaluate (3.37). Since k1 and k2 are of half the bitlength of k, half of the point doublings are eliminated. The strategy is effective provided that a decomposition (3.36) and φ ( P) can be computed efficiently.

Decomposing a multiplier

We describe one method for obtaining a balanced length-two representation of the multiplier k. For a vector v = (a, b) Z × Z, define

f (v) = a + bλ mod n.

The idea is to first find two vectors, v1 = (a1, b1) and v2 = (a2, b2) in Z × Z such that

Then, by considering (k, 0) as a vector in Q × Q, we can use elementary linear algebra to write

(k, 0) = γ1v1 + γ2v2, where γ1, γ2 Q.

If we let c1 = γ1 and c2 = γ2 , where x denotes the integer closest to x, then v = c1v1 + c2v2 is an integer-valued vector close to (k, 0) such that f (v) = 0. Thus the vector u = (k, 0) − v has small norm and satisfies f (u) = k. It follows that the components k1, k2 of u are small in absolute value and satisfy k1 + k2λ ≡ k (mod n).

The independent short vectors v1 and v2 satisfying f (v1) = f (v2) = 0 can be found by applying the extended Euclidean algorithm (Algorithm 2.19) to n and λ. The algorithm produces a sequences of equations si n + ti λ = ri where s0 = 1, t0 = 0, r0 = n, s1 = 0, t1 = 1, r1 = λ. Furthermore, it is easy to show that the remainders ri are strictly decreasing and non-negative, that |ti | < |ti+1| for i ≥ 0, and that |si | < |si+1| and

and that v2 = (rl , −tl ) (and also v2 = (rl+2, −tl+2)) is linearly independent of v1 and satisfies f (v2) = 0. Heuristically, we would expect v2 to have small norm. Thus v1 and v2 satisfy conditions 1–3 above. For this choice of v1, v2, we have γ1 = b2k/n and γ2 = −b1k/n. The method for decomposing k is summarized in Algorithm 3.74.

Algorithm 3.74 Balanced length-two representation of a multiplier

INPUT: Integers n, λ, k [0, n − 1]. √ OUTPUT: Integers k1, k2 such that k = k1 + k2λ mod n and |k1|, |k2| ≈ n.

1. Run the extended Euclidean algorithm (Algorithm 2.19) with inputs n and λ. The algorithm produces a sequence of equations si n + ti λ = ri where s0 = 1, t0 = 0,

r = n, s = 0, t = 1, r = λ, and the remainders r and are non-negative and

0 1 1 1 i √

strictly decreasing. Let l be the greatest index for which rl ≥ n.

2.Set (a1, b1) ← (rl+1, −tl+1).

3.If (rl2 + tl2) ≤ (rl2+2 + tl2+2) then set (a2, b2) ← (rl , −tl ); Else set (a2, b2) ← (rl+2, −tl+2).

4.Compute c1 = b2k/n and c2 = −b1k/n .

5.Compute k1 = k − c1a1 − c2a2 and k2 = −c1b1 − c2b2.

6.Return(k1 , k2).

Example 3.75 (balanced length-two representation of a multiplier k) Consider the elliptic curve P-160 defined in Example 3.73. In the notation of Algorithm 3.74 we have

(rl , tl ) = (2180728751409538655993509, −186029539167685199353061) (rl+1, tl+1) = (788919430192407951782190, 602889891024722752429129) (rl+2, tl+2) = (602889891024722752429129, −1391809321217130704211319)

(a1, b1) = (788919430192407951782190, −602889891024722752429129) (a2, b2) = (602889891024722752429129, 1391809321217130704211319).

Now, let

k = 965486288327218559097909069724275579360008398257.