What is Binary Exponentiation?

Binary Exponentiation (also called Fast Exponentiation or exponentiation by squaring) is an algorithm that computes $a^{b}$ in O(log b) multiplications, instead of the naive $O (b)$ linear loop. It is a fundamental tool for cryptography (RSA), modular arithmetic reduction, and computing large linear recurrences via matrix exponentiation.

Mathematical Proof of Correctness

We want to prove that the recursive formula:
$P (a, b) = ⎩ ⎨ ⎧ 1 P (a, b /2)^{2} a \cdot P (a, (b - 1) /2)^{2} if b = 0 if b > 0 and b is even if b > 0 and b is odd$
correctly computes $a^{b}$ for all integers $b \geq 0$ .
Proof by Induction:
- Base Case: For $b = 0$ , $P (a, 0) = 1 = a^{0}$ . The base case holds.
- Inductive Step: Assume the formula is correct for all exponents smaller than $b$ . We show it holds for $b$ :
  - Case 1: $b$ is even ( $b = 2 k$ ) $P (a, 2 k) = P (a, k)^{2}$ By the induction hypothesis, $P (a, k) = a^{k}$ . Therefore: $P (a, 2 k) = (a^{k})^{2} = a^{2 k} = a^{b}$
  - Case 2: $b$ is odd ( $b = 2 k + 1$ ) $P (a, 2 k + 1) = a \cdot P (a, k)^{2}$ By the induction hypothesis, $P (a, k) = a^{k}$ . Therefore: $P (a, 2 k + 1) = a \cdot (a^{k})^{2} = a \cdot a^{2 k} = a^{2 k + 1} = a^{b}$ In both cases, $P (a, b) = a^{b}$ . By mathematical induction, the algorithm is correct. Q.E.D.

Modular Exponentiation & Exponent Reduction

1. Modular Exponentiation

To calculate $(a^{b} mod m)$ , we apply the modulus operator at every multiplication:
$(x \cdot y) mod m = ((x mod m) \cdot (y mod m)) mod m$
This ensures that our intermediate products never exceed $m^{2}$ , preventing integer overflow.

2. Exponent Reduction via Euler’s Totient Theorem

If the exponent $b$ is extremely large (e.g. $b = 1 0^{100}$ or $b = 2^{2^{N}}$ ), we cannot compute it directly. However, if $g cd (a, m) = 1$ , we can reduce the exponent using Euler’s Totient Theorem:
$a^{ϕ (m)} \equiv 1 (mod m)$
where $ϕ (m)$ is Euler’s Totient Function (the number of integers up to $m$ coprime to $m$ ).
Consequently, we can reduce the exponent $b$ modulo $ϕ (m)$ :
$a^{b} \equiv a^{b mod ϕ (m)} (mod m)$

Special Case: Fermat’s Little Theorem

If the modulus $p$ is a prime number, then $ϕ (p) = p - 1$ .
If $g cd (a, p) = 1$ , the reduction simplifies to Fermat’s Little Theorem:
$a^{p - 1} \equiv 1 (mod p) ⟹ a^{b} \equiv a^{b mod (p - 1)} (mod p)$

Matrix Exponentiation (Deep Dive)

1. Linear Recurrence Generalization

Suppose we have a homogeneous linear recurrence of order $k$ :
$F_{n} = c_{1} F_{n - 1} + c_{2} F_{n - 2} + \dots + c_{k} F_{n - k}$
We can represent the state transition as a vector-matrix multiplication:
$F_{n} F_{n - 1} F_{n - 2} ⋮ F_{n - k + 1} = c_{1} 10 ⋮ 0 c_{2} 01 ⋮ 0 c_{3} 00 ⋮ \dots \dots \dots \dots ⋱ 1 c_{k} 00 ⋮ 0 \cdot F_{n - 1} F_{n - 2} F_{n - 3} ⋮ F_{n - k}$
Let $S_{n}$ be the state vector $(F_{n} F_{n - 1} \dots F_{n - k + 1})^{T}$ , and $T$ be the $k \times k$ transition matrix.
$S_{n} = T \cdot S_{n - 1}$
By induction, we can compute the $n$ -th state vector directly from the base state $S_{k - 1}$ :
$S_{n} = T^{n - k + 1} \cdot S_{k - 1}$
Since we can compute $T^{n - k + 1}$ in $O (k^{3} lo g n)$ matrix multiplications using binary exponentiation, we can find the $n$ -th term of any linear recurrence in logarithmic time.

2. Example: Tribonacci Numbers

The Tribonacci sequence is defined as: $T_{n} = T_{n - 1} + T_{n - 2} + T_{n - 3} with T_{0} = 0, T_{1} = 0, T_{2} = 1$
The transition matrix $T$ is: $T = 110101100$
To find the $n$ -th Tribonacci number, we compute: $T_{n} T_{n - 1} T_{n - 2} = 110101100^{n - 2} \cdot T_{2} T_{1} T_{0}$

Time & Space Complexity

Complexity Table

Implementation	Time Complexity	Space Complexity	Details
Standard Power	$O (lo g b)$	$O (lo g b)$ recursive / $O (1)$ iterative	Halves exponent size at each step
Modular Power	$O (lo g b)$	$O (1)$ iterative	Numbers kept small by modulus $m$
Matrix Power	$O (K^{3} lo g N)$	$O (K^{2})$	$K \times K$ matrix size

Implementation

Below are the implementations for iterative Modular Exponentiation and 2x2 Matrix Exponentiation (to compute Fibonacci). Python · Cpp · Java Script · Java

Languages:

# 1. Iterative Modular Exponentiation: (a^b) % m
def bin_pow(a, b, m):
    res = 1
    a = a % m
    while b > 0:
        if b & 1:
            res = (res * a) % m
        a = (a * a) % m
        b >>= 1
    return res
 
# 2. Matrix Multiplication Helper
def multiply_matrix(A, B, m):
    C = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % m
    return C
 
# 3. Matrix Exponentiation to get Fibonacci F_N % m
def fibonacci_matrix(n, m):
    if n == 0:
        return 0
    # Transition matrix T = [[1, 1], [1, 0]]
    T = [[1, 1], [1, 0]]
    # Identity matrix I
    I = [[1, 0], [0, 1]]
    
    # Power transition matrix to T^(n-1)
    power = n - 1
    while power > 0:
        if power & 1:
            I = multiply_matrix(I, T, m)
        T = multiply_matrix(T, T, m)
        power >>= 1
    # F_n is I[0][0]
    return I[0][0]
 
# Example usage
print("3^13 % 1000000007 =", bin_pow(3, 13, 1000000007))
print("10th Fibonacci % 10007 =", fibonacci_matrix(10, 10007))  # 55

#include <iostream>
#include <vector>
 
// 1. Iterative Modular Exponentiation: (a^b) % m
long long bin_pow(long long a, long long b, long long m) {
    long long res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1)
            res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}
 
typedef std::vector<std::vector<long long>> Matrix;
 
// Helper to multiply 2x2 matrices
Matrix multiply(const Matrix& A, const Matrix& B, long long m) {
    Matrix C(2, std::vector<long long>(2, 0));
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % m;
            }
        }
    }
    return C;
}
 
// 2. Matrix Exponentiation to get Fibonacci F_N % m
long long fibonacci_matrix(long long n, long long m) {
    if (n == 0) return 0;
    Matrix T = {{1, 1}, {1, 0}};
    Matrix I = {{1, 0}, {0, 1}};
 
    long long power = n - 1;
    while (power > 0) {
        if (power & 1)
            I = multiply(I, T, m);
        T = multiply(T, T, m);
        power >>= 1;
    }
    return I[0][0];
}
 
int main() {
    std::cout << "3^13 % 1000000007 = " << bin_pow(3, 13, 1000000007) << "\n";
    std::cout << "10th Fibonacci % 10007 = " << fibonacci_matrix(10, 10007) << "\n";
    return 0;
}

// 1. Iterative Modular Exponentiation: (a^b) % m using BigInt for safety
function binPow(a, b, m) {
    let res = 1n;
    a = BigInt(a) % BigInt(m);
    b = BigInt(b);
    const mod = BigInt(m);
    
    while (b > 0n) {
        if (b & 1n) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1n;
    }
    return Number(res);
}
 
// Helper to multiply 2x2 matrices
function multiply(A, B, m) {
    const C = [[0n, 0n], [0n, 0n]];
    const mod = BigInt(m);
    for (let i = 0; i < 2; i++) {
        for (let j = 0; j < 2; j++) {
            for (let k = 0; k < 2; k++) {
                C[i][j] = (C[i][j] + BigInt(A[i][k]) * BigInt(B[k][j])) % mod;
            }
        }
    }
    return C;
}
 
// 2. Matrix Exponentiation to get Fibonacci F_N % m
function fibonacciMatrix(n, m) {
    if (n === 0) return 0;
    let T = [[1n, 1n], [1n, 0n]];
    let I = [[1n, 0n], [0n, 1n]];
 
    let power = BigInt(n - 1);
    while (power > 0n) {
        if (power & 1n) {
            I = multiply(I, T, m);
        }
        T = multiply(T, T, m);
        power >>= 1n;
    }
    return Number(I[0][0]);
}
 
console.log("3^13 % 1000000007 =", binPow(3, 13, 1000000007));
console.log("10th Fibonacci % 10007 =", fibonacciMatrix(10, 10007));

import java.util.*;
 
public class BinaryExponentiation {
 
    // 1. Iterative Modular Exponentiation: (a^b) % m
    public static long binPow(long a, long b, long m) {
        long res = 1;
        a %= m;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res * a) % m;
            }
            a = (a * a) % m;
            b >>= 1;
        }
        return res;
    }
 
    // Helper to multiply 2x2 matrices
    private static long[][] multiply(long[][] A, long[][] B, long m) {
        long[][] C = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % m;
                }
            }
        }
        return C;
    }
 
    // 2. Matrix Exponentiation to get Fibonacci F_N % m
    public static long fibonacciMatrix(long n, long m) {
        if (n == 0) return 0;
        long[][] T = {{1, 1}, {1, 0}};
        long[][] I = {{1, 0}, {0, 1}};
 
        long power = n - 1;
        while (power > 0) {
            if ((power & 1) == 1) {
                I = multiply(I, T, m);
            }
            T = multiply(T, T, m);
            power >>= 1;
        }
        return I[0][0];
        }
 
    public static void main(String[] args) {
        System.out.println("3^13 % 1000000007 = " + binPow(3, 13, 1000000007));
        System.out.println("10th Fibonacci % 10007 = " + fibonacciMatrix(10, 10007));
    }
}

Key Takeaways

Logarithmic Exponentiation — Halving the exponent size at each step by squaring the base reduces linear multiplication loops $O (b)$ to $O (lo g b)$ operations.
Modular Safety & Euler Reduction — Modular multiplication prevents overflow. Euler’s Totient Theorem ( $a^{b} \equiv a^{b mod ϕ (m)} (mod m)$ ) enables reducing massive exponent terms.
Matrix Recurrence Solving — Linear homogeneous recurrences (e.g. Fibonacci, Tribonacci) are solvable in $O (k^{3} lo g N)$ time by exponentiating the transition matrix $T$ .

More Learn

GitHub & Webs

Euclidean Algorithm for GCD – Extended GCD and modular inverse
Sieve of Eratosthenes – Fast prime generation
DSA Algo & System Design – Full DSA index

Table of Contents

Explorer

Binary Exponentiation Algorithm

Mathematical Proof of Correctness

Modular Exponentiation & Exponent Reduction

1. Modular Exponentiation

2. Exponent Reduction via Euler’s Totient Theorem

Special Case: Fermat’s Little Theorem

Matrix Exponentiation (Deep Dive)

1. Linear Recurrence Generalization

2. Example: Tribonacci Numbers

Time & Space Complexity

Complexity Table

Implementation

Key Takeaways

More Learn

GitHub & Webs

Related Pages

Enjoying the Notes?

Graph View

Backlinks

Recently Updated