Solution to Exercise 1.26:

Because Louis’s version makes two calls to expmod for the even case instead of one, his process comes to resemble a binary tree of depth log n. The original creates a process that resembled a chain of length log n. When we count the number of nodes in Louis’s binary tree we get n - 1, bringing it back to Θ(n).

Posted by Ken Dyck in Programming