[This page is auto-generated; please prefer to read the article’s PDF Form.]
Given two positive integers a and b, we need to compute ab. Here, a is called the Base, b the Exponent and this process Exponentiation. A related process is Modular Exponentiation, where we are also given positive integer n called the Modulus, and need to compute ab mod n. In this article, we will discuss some algorithms which will apply to both these processes with slight changes.
On a computer system which can handle integers only up to 64 bits, the set of integers a and b so that ab can fit in a single hardware provided 64-bit integer is very limited. For example, to ensure ab < 264 for any a ≥ 2, b must be less than 64. For a ≥ 256 (= 28), b must be less than 8. To perform exponentiation for larger integers a and b, we will need a software level support for handling arbitrarily large integers and arithmetic over them.
The algorithms we discuss here are applicable to any positive integers a, b and n, however large they may be. But the source code shown for them will only use int and long type of C, which are restricted in their range of integers. This allows to keep the source code simpler while we discuss the mathematics behind the algorithms. With help of a large-integers software library, this source code can be adjusted to support arbitrarily large integers.
We will be frequently using the binary representation of b. We can denote it by (bm−1bm−2…b1b0)2, which has m bits for some m ≥ 1. Since b > 0, the most-significant-bit bm−1 must be 1. We will say bit bp is at Position p. “MSB” and “LSB” will be used to refer to the most and least-significant-bit. Due to the way this binary form is written, leftmost and rightmost bits will mean MSB and LSB respectively. Also, a prefix (or suffix) of this binary form will mean sequence of bits starting at the MSB (or ending at the LSB).
[Next]
Copyright © 2021 Nitin Verma. All rights reserved.