Exponentiation is the operation of raising one variable to the power of another; for example,ab. 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.
7.1 Exponentiation Basics
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˜ 21024, as is the case when ...