Question

Devise a recursive algorithm for finding xⁿ (mod m) whenever n, x and m are positive integers. Also prove that your algorithm is correct.

You should use the fact that xⁿ (mod m) = (xⁿ−¹ (mod m) · x (mod m)) (mod m).

Answer 1

By induction, the algorithm correctly returns
`x^n` (mod m) for any positive integer n.

Here's the recursive algorithm for finding xⁿ (mod m):

def modular_exponentiation(x, n, m):

if n == 0:

return 1 % m

elif n % 2 == 0:

return (modular_exponentiation(x, n // 2, m) * modular_exponentiation(x, n // 2, m)) % m

else:

return (x * modular_exponentiation(x, n - 1, m)) % m

To prove the correctness of this algorithm, we can use induction:

Base case: n = 0. The algorithm correctly returns 1 (mod m).

Induction step: Assume the algorithm correctly computes xⁿ (mod m) for n = k, where k is a non-negative integer.

We need to prove that it also correctly computes
`x^(k+1)` (mod m).

Using the given formula, x^(k+1) (mod m) = (
`x^k` (mod m) * x (mod m)) (mod m).

We know that the algorithm correctly computes
`x^k` (mod m) from the induction hypothesis.

Substituting that into the equation, we get:

`x^(k+1)` (mod m) = ((modular_exponentiation(x, k, m)) (mod m) * x (mod m)) (mod m)

Since modular exponentiation is associative, we can rearrange the parentheses without changing the result:

`x^(k+1)` (mod m) = (x (mod m) * (modular_exponentiation(x, k, m)) (mod m)) (mod m)

Since multiplication is commutative, we can swap the order of the operands:

`x^(k+1)` (mod m) = (modular_exponentiation(x, k, m) (mod m) * x (mod m)) (mod m)

This is exactly the recursive formula used in the algorithm, so the algorithm correctly computes
`x^(k+1)` (mod m).

Therefore, by induction, the algorithm correctly computes xⁿ (mod m) for all non-negative integers n.