17.1.2: The Invariant Relation Theorem

Exponentiation Algorithms

Consider the following algorithm implemented in Sage to compute \(a^m mod \, n\text{,}\) given an arbitrary integer \(a\text{,}\) non-negative exponent \(m\text{,}\) and a modulus \(n\text{,}\) \(n \ge 0\text{.}\) The default sample evaluation computes \(2^5\, mod\,7 = 32\,mod\,7 = 4\text{,}\) but you can edit the final line for other inputs.

def slow_exp(a,m,n):
    b=1
    k=m
    while k>0:
        b=(b*a)%n  # % is integer remainder (mod) operation
        k-=1
    return b
slow_exp(2,5,7)

It should be fairly clear that this algorithm will successfully compute \(a^m (mod\, n)\) since it mimics the basic definition of exponentiation. However, this algorithm is highly inefficient. The algorithm that is most commonly used for the task of exponentiation is the following one, also implemented in Sage.

def fast_exp(a,m,n):
    t=a
    b=1
    k=m
    while k>0:
        if k%2==1: b=(b*t)%n
        t=(t^2)%n
        k=k//2  # // is the integer quotient operation
    return b    
fast_exp(2,5,7)

The only difficulty with the "fast algorithm" is that it might not be so obvious that it always works. When implemented, it can be verified by example, but an even more rigorous verification can be done using the Invariant Relation Theorem. Before stating the theorem, we define some terminology.

17.1.2.2: Proving the Correctness of the Fast Algorithm

Definition \(\PageIndex{1}\): Pre and Post Values

Given a variable \(x\text{,}\) the pre value of \(x\text{,}\) denoted \(\grave x\text{,}\) is the value before an iteration of a loop. The post value, denoted \(\acute x\text{,}\) is the value after the iteration.

Example \(\PageIndex{1}\): Pre and Post Values in the Fast Exponentiation Algorithm

In the fast exponentiation algorithm, the relationships between the pre and post values of the three variables are as follows.

\begin{equation*} \acute{b} \equiv \grave{b} \grave{t}^{\grave{k} mod\,2}(mod\, n) \end{equation*}

\begin{equation*} \acute{t} \equiv \grave t^2(mod\,n) \end{equation*}

\begin{equation*} \acute k = \grave k//2 \end{equation*}

Definition \(\PageIndex{2}\): Invariant Relation

Given an algorithm's inputs and a set of variables that are used in the algorithm, an invariant relation is a set of one or more equations that are true prior to entering a loop and remain true in every iteration of the loop.

Example \(\PageIndex{2}\): Invariant Relation for Fast Exponentiation

We claim that the invariant relation in the fast algorithm is \(b t^k = a^m (mod\,n)\text{.}\) We will prove that this is indeed true below.

Theorem \(\PageIndex{1}\): The Invariant Relation Theorem

Given a loop within an algorithm, if \(R\) is a relation with the properties

1. R is true before entering the loop
2. the truth of R is maintained in any iteration of the loop
3. the condition for exiting the loop will always be reached in a finite number of iterations.

then R will be true upon exiting the loop.

Proof

The condition that the loop ends in a finite number of iterations lets us apply mathematical induction with the induction variable being the number of iterations. We leave the details to the reader.

We can verify the correctness of the fast exponentiation algorithm using the Invariant Relation Theorem. First we note that prior to entering the loop, \(b t^k = 1 a^m = a^m (mod\,n)\text{.}\) Assuming the relation is true at the start of any iteration, that is \(\grave{b} \grave{t}^{\grave k} = a^m (mod\,n)\text{,}\) then

\begin{equation*} \begin{split} \acute{b} \acute{t}^{\acute{k}} & \equiv (\grave{b} \grave{t}^{\grave{k}\,mod\,2})(\grave t^2)^{ \grave k//2}(mod\,n)\\ & \equiv\grave{b} \grave{t}^{2(\grave{k}//2) +\grave{k}\,mod\,2 }(mod\,n) \\ & \equiv \grave{b} \grave{t}^{\grave{k}}(mod\,n)\\ & \equiv a^m (mod\,n) \end{split} \end{equation*}

Finally, the value of \(k\) will decrease to zero in a finite number of steps because the number of binary digits of \(k\) decreases by one with each iteration. At the end of the loop,

\begin{equation*} b = b t^0 = b t^k \equiv a^m(mod\,n) \end{equation*}

which verifies the correctness of the algorithm.

Exercises

Exercise \(\PageIndex{1}\)

How are the pre and post values in the slow exponentiation algorithm related? What is the invariant relation between the variables in the slow algorithm?

Exercise \(\PageIndex{2}\)

Verify the correctness of the following algorithm to compute the greatest common divisor of two integers that are not both zero.

def gcd(a,b):
    r0=a
    r1=b
    while r1 !=0:
        t= r0 % r1
        r0=r1
        r1=t
    return r0
gcd(1001,154)  #test

Hint

The invariant of this algorithm is \(gcd(r0,r1)=gcd(a,b)\text{.}\)

Exercise \(\PageIndex{3}\)

Verify the correctness of the Binary Conversion Algorithm, Algorithm 1.4.1, in Chapter 1.