Binary Exponentiation

Synonyms

Square-and-multiply exponentiation

Related Concepts

Exponentiation Algorithms

Definition

The binary exponentiation method computes powers directed by the exponent bits, one at a time. Bits of value 0 require a squaring; bits of value 1 require a squaring and a multiplication.

Background

Most schemes for public key cryptography involve exponentiation in some group (or, more generally, in some semigroup: an algebraic structure like a group except that elements need not have inverses, and that there may not even be an identity element). The term exponentiation assumes that the group operation is written multiplicatively. If the group operation is written additively, one speaks of scalar multiplication instead, but this change in terminology does not affect the essence of the task.

Let ∘ denote the group operation and assume that the exponentiation to be performed is g ^e where g is an element of the group (or semigroup) and e is a positive integer. Computing the result \(g \circ...