How does the Fast Modular Exponentiation Algorithm handle recursive calls?

Question

I have been taught the Fast Modular Exponentiation Algorithm as shown below.

FastExponentiation(a, p, n):
  if p = 0 then
    return 1
  if p is even then
    t <- FastExponentiation(a, p/2, n)
    return t^2 mod n
  t <- FastExponentiation(a, (p-1)/2, n)
  return a(t^2 mod n) mod n

How do the second and third return statements ever get reached when running this program? There is a recursive call before these two statements so surely the program would just enter a recursive loop?

Answer 1

The snippet below can illustrate you how p decreases while going deeper into the recursion, until it becomes 1. On the next recursive call it becomes zero: (1-1)/2 → 0.

function fastExp (a, p, n, level = 0, pExpr = '') {
    if (level == 0) {
        console.log(`Fast exponentiation: ${a} ^ ${p} mod ${n}`);
    }
    console.log(`${'  '.repeat(level)}> p = ${pExpr}${p}`);
    let res;
    if (p == 0) {
        res = 1;
    }
    else if ((p & 1) == 0) {
        let t = fastExp(a, p/2, n, level+1, `${p}/2 = `);
        res = (t*t) % n;
    }
    else {
        let t = fastExp(a, (p-1)/2, n, level+1, `(${p}-1)/2 = `);
        res = (a * ((t*t) % n)) % n;
    }
    console.log(`${'  '.repeat(level)}> ${a} ^ ${p} mod ${n} = ${res}`);
    return res;
}

function rand () { return Math.floor(Math.random() * 50) + 50; }
fastExp(rand(), rand(), rand());