11 - Basic algorithms for algebraic groups

Summary

In Section 4.1 a number of basic computational tasks for an algebraic group G were listed. Some of these topics have been discussed already, especially providing efficient group operations and compact representations for group elements. But some other topics (such as efficient exponentiation, generating random elements in G and hashing from or into G) require further attention. The goal of this chapter is to briefly give some details about these tasks for the algebraic groups of most interest in the book.

The main goal of the chapter is to discuss exponentiation and multi-exponentiation. These operations are crucial for efficient discrete logarithm cryptography and there are a number of techniques available for specific groups that give performance improvements.

It is beyond the scope of this book to present a recipe for the best possible exponentiation algorithm in a specific application. Instead, our focus is on explaining the mathematical ideas that are used. For an “implementors guide” in the case of elliptic curves we refer to Bernstein and Lange [51].

Let G be a group (written in multiplicative notation). Given g ∈ G and a ∈ ℕ we wish to compute g^a. We assume in this chapter that a is a randomly chosen integer of size approximately the same as the order of g, and so a varies between executions of the exponentiation algorithm. If g does not change between executions of the algorithm then we call it a fixed base and otherwise it is a variable base.