Some Algorithms for Exponentiation: Common Structure in Algorithms

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Common Structure in Algorithms

In all the algorithms we discuss below, we can observe a common structure. All of them build-up the value of a^b (modulo n) iteratively, where an integer x initialized as 0 or 1 is updated to a higher integer (or kept intact) in each iteration. The loop is terminated when x becomes b. The desired computation of a^b is performed in integer variable r, by maintaining the following loop-invariant in each iteration:

P : r = ax mod n

So, when the loop terminates with x = b, we must have r = a^b mod n. This common structure can be expressed in pseudocode as:

x <- 0 (or 1)

r <- a^0 (or a^1) mod n

while(x < b)
{
increase x to some higher integer.

update r to maintain P for the new x.
}

The individual algorithms will diﬀer in how the value of x is built-up iteratively to become b, and correspondingly how r is updated to maintain invariant P for the updated x.

We will also see that, though x helps in specifying the invariants and is critical in understanding the working of the algorithms, its presence is not really required for actual execution of the algorithms.

We will now discuss the algorithms individually.

[Prev] [Up] [Next]