Elliptic Curves over Finite Fields - Elliptic Curves: Number Theory and Cryptography - page 131

An attractive feature of supersingular curves is that computations involving
an integer times a point can sometimes be done faster than might be expected.
Suppose E is a supersingular elliptic curve defined over F q and let P =( x, y )
be a point in E ( F q n )forsome n 1. Usually n is large. Let k be a positive

integer. We want to compute kP . This can be done quickly by successive
doubling, but it is possible to do even better. Let's assume that a =0. Then

≥

φ q + q =0

by Theorem 4.10. Therefore
q ( x, y )= −φ q ( x, y )= x q 2 , −y q 2 .

The calculations of x q 2 and y q 2 involve finite field arithmetic, which is gener-
ally faster than elliptic curve calculations. Moreover, if x and y are expressed
in terms of a normal basis of F q n over F q ,then x q 2 and y q 2 are computed by
shift operations (see Appendix C). The procedure is now as follows:

1. Expand k in base q :

k = k 0 + k 1 q + k 2 q 2 + ··· + k r q r ,

with 0 ≤ k i <q .

2. Compute k i P =( x i ,y i )foreach i .

3. Compute q i k i P =( x q 2 i 1) i y q 2 i , ( − ).

i i

4. Sum the points q i k i P for 0 ≤ i ≤ r .

The main savings is in step (3), where elliptic curve calculations are replaced
by finite field computations.
We now show how to obtain all supersingular curves over F q . Note that
supersingularity means that there are no points of order p with coordinates
in the algebraic closure; hence, it is really a property of an elliptic curve over
an algebraically closed field. If we have two elliptic curves E 1 and E 2 defined
over a field such that E 1 can be transformed into E 2 by a change of variables
defined over some extension field, then E 1 is supersingular if and only if E 2
is supersingular.
For example, in Proposition 4.33, the curve y 1 = x 1 + B can be changed
into y 2 = x 2 + 1 via x 2 = x 1 /B 1 / 3 ,y 2 = y 1 /B 1 / 2 . Therefore, it would have
suced to prove the proposition for the curve y 2 = x 3 +1.
Recall (Section 2.5.1) that an elliptic curve E over an algebraically closed
field of characteristic not 2 can be put into the Legendre form y 2 = x ( x −

1)( x − λ )with λ =0 , 1.