Basic algorithms for algebraic groups - Mathematics of Public Key Cryptography - page 221

simultaneously zero relatively often. Such a method was developed by Solinas [ 518 ] and
is called a joint sparse form . We refer to Section 9.1.5 of [ 16 ] and Section 3.3.3 of [ 248 ].

Multi-exponentiation for algebraic group quotients
In algebraic group quotients, multiplication is not well-defined and so extra information
is needed to be able to compute i = 1 g a i . A large survey of exponentiation algorithms
and multi-exponentiation algorithms for algebraic group quotients is given in Chapter 3 of
Stam's thesis [ 520 ]. In particular, he gives the Montgomery Euclidean ladder in Section 3.3
(also see Section 4.3 of [ 519 ]). Due to lack of space we do not discuss this topic further.

11.3 Efficient exponentiation in specific algebraic groups

We now discuss some exponentiation methods that exploit specific features of algebraic
groups.

11.3.1 Alternative basic operations

So far, all exponentiation algorithms have been based on squaring (and hence have used
representations of integers to the base 2). We now briefly mention some alternatives to
squaring as the basic operation. First, we discuss halving and tripling. Frobenius expansions
will be discussed in Section 11.3.2 .
When one has several possible basic operations then one can consider multi-base rep-
resentations of integers for exponentiation. These ideas were first proposed by Dimitrov,
Jullien and Miller [ 167 ], but we do not consider them further in this topic.

Point halving on elliptic curves
This idea, independently discovered by Knudsen [ 307 ] and Schroeppel, applies to sub-
groups of odd order in ordinary elliptic curves over finite fields of characteristic 2. The
formulae for point halving were given in Exercise 9.1.4 :given P = ( x P ,y P ) ∈ E ( F 2 n )

P by solving λ 2 Q +

one finds Q = ( x Q ,y Q ) ∈ E ( F 2 n ) such that [2] Q = λ Q = x P + a 2 .

For either solution let x Q = x P ( λ Q + y P = x P ( λ P +

1) + λ Q + x P + 1) and y Q =

x Q ( λ Q + x Q ). One must ensure that the resulting point Q has odd order. When 2 # E ( F q n )

this is easy as, by Exercise 9.1.4 , it is sufficient to check that Tr F 2 n / F 2 ( x Q ) = Tr F 2 n / F 2 ( a 2 ).

In practice, it is more convenient to check whether Tr F 2 n / F 2 ( x Q ) Tr F 2 n / F 2 ( a 2 ). =

Exercise 11.3.1 Write down the point halving algorithm.

Knudsen suggests representing points using the pair ( x P ,λ P ) instead of ( x P ,y P ). In any
case, this can be done internally in the exponentiation algorithm. When

F 2 n is represented

using a normal basis over F 2 then halving can be more efficient than doubling on such an

elliptic curve. One can therefore use expansions of integers to the “base 2 − 1 ” for efficient
exponentiation. We refer to Section 13.3.5 of [ 16 ] and [ 307 ] for the details.