TABLE OF CONTENTS Exponentiation is the operation of raising one variable to the power of another; for example, a b. A variant of exponentiation, computed in a finite field or ring, is called modular exponentiation. This latter style of operation is typically used in public key cryptosystems such as RSA and Diffie-Hellman. The ability to quickly compute modular exponentiations is of great benefit to any such cryptosystem, and many methods have been sought to speed it up.
A trivial algorithm would simply multiply a against itself b-1 times to compute the exponentiation desired. However, as b grows in size the number of multiplications becomes prohibitive. Imagine what would happen if b ~ 2 1024, as is the case when computing an RSA signature with a 1024-bit key. Such a calculation could never be completed, as it would take far too long.
Fortunately, there is a very simple algorithm based on the laws of exponents. Recall that lg a( a b) = b and that lg a( a ba c) = b+c which are two trivial relationships between the base and the exponent. Let b i represent the i'th bit of b starting from the least significant bit. If b is a k-bit integer, equation 7.1 is true.
| (7.1) |  |
By taking the base a logarithm of both sides of the equation, equation 7.2 is the result.
| (7.2) |  |
The term 
can...
