828 Intermediate

Modular Exponentiation

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Modular Exponentiation" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Computing a^b mod m naively multiplies a together b times, requiring O(b) operations — impractical for b = 10^18. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Computing a^b mod m naively multiplies a together b times, requiring O(b) operations — impractical for b = 10^18. Fast modular exponentiation (binary exponentiation / repeated squaring) achieves O(log b) by decomposing the exponent in binary: if b is even, a^b = (a^(b/2))^2; if odd, a^b = a * a^(b-1). This is the core operation in RSA encryption/decryption (a^e mod n, a^d mod n), Diffie-Hellman key exchange, primality testing (Fermat, Miller-Rabin), and computing large Fibonacci numbers via matrix exponentiation. Without it, public-key cryptography would be computationally infeasible.

🎯 Learning Outcomes

• Implement binary exponentiation iteratively: scan bits of exponent from LSB to MSB

• Understand why O(log b) squarings suffice: the exponent halves at each step

• Extend to matrix exponentiation: same algorithm works with matrix multiplication replacing integer multiplication

• Apply Fermat's little theorem: a^(p-1) ≡ 1 (mod p) for prime p implies a^(-1) ≡ a^(p-2) (mod p)

• Recognize the connection: fast power → modular inverse → modular division

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Fast Modular Exponentiation in OCaml *)

(* Recursive binary method — elegant and clear *)
let rec pow_mod_rec (base : int) (exp : int) (m : int) : int =
  if exp = 0 then 1 mod m
  else if exp land 1 = 1 then
    (* Odd exponent: a^n = a * a^(n-1) *)
    let rest = pow_mod_rec base (exp - 1) m in
    Int64.(to_int (rem (mul (of_int base) (of_int rest)) (of_int m)))
  else
    (* Even exponent: a^n = (a^(n/2))^2 *)
    let half = pow_mod_rec base (exp / 2) m in
    Int64.(to_int (rem (mul (of_int half) (of_int half)) (of_int m)))

(* Iterative binary method — more efficient (no stack) *)
let pow_mod (base : int) (exp : int) (m : int) : int =
  let result = ref 1 in
  let base = ref (base mod m) in
  let exp = ref exp in
  while !exp > 0 do
    if !exp land 1 = 1 then
      result := Int64.(to_int (rem (mul (of_int !result) (of_int !base)) (of_int m)));
    base := Int64.(to_int (rem (mul (of_int !base) (of_int !base)) (of_int m)));
    exp := !exp lsr 1
  done;
  !result

(* Matrix exponentiation for Fibonacci — shows generality of the method *)
(* M^n via binary exponentiation where M is a 2x2 matrix *)
type matrix = { a: int; b: int; c: int; d: int }

let mat_mul m1 m2 modp =
  let mm a b = Int64.(to_int (rem (mul (of_int a) (of_int b)) (of_int modp))) in
  { a = (mm m1.a m2.a + mm m1.b m2.c) mod modp;
    b = (mm m1.a m2.b + mm m1.b m2.d) mod modp;
    c = (mm m1.c m2.a + mm m1.d m2.c) mod modp;
    d = (mm m1.c m2.b + mm m1.d m2.d) mod modp }

let mat_id = { a=1; b=0; c=0; d=1 }

let rec mat_pow m exp modp =
  if exp = 0 then mat_id
  else if exp land 1 = 1 then mat_mul m (mat_pow m (exp-1) modp) modp
  else let half = mat_pow m (exp/2) modp in mat_mul half half modp

(* F(n) mod p using matrix exponentiation in O(log n) *)
let fib_mod n p =
  if n = 0 then 0
  else
    let m = mat_pow { a=1; b=1; c=1; d=0 } (n-1) p in
    m.a

let () =
  Printf.printf "2^10 mod 1000 = %d  (expected 24)\n" (pow_mod 2 10 1000);
  Printf.printf "3^100 mod 1_000_000_007 = %d\n" (pow_mod 3 100 1_000_000_007);
  Printf.printf "2^1000 mod 1009 = %d\n" (pow_mod 2 1000 1009);
  Printf.printf "recursive: 2^10 mod 1000 = %d\n" (pow_mod_rec 2 10 1000);
  Printf.printf "fib(10) mod 100 = %d  (expected 55)\n" (fib_mod 10 100);
  Printf.printf "fib(100) mod 1_000_000_007 = %d\n" (fib_mod 100 1_000_000_007)

Key Differences

Aspect	Rust	OCaml
Overflow handling	Explicit `as u128` cast	`Int64` or `Zarith`
Style	Iterative while loop	Recursive or iterative
Edge cases	`exp = 0` → returns 1 naturally	Same
Matrix variant	Generic `fn mat_pow<T: Mul>`	Functor over ring type
Modular inverse	`mod_pow(a, p-2, p)` for prime p	Same
Largest safe modulus	~9.2 * 10^18 (u64)	~4.6 * 10^18 (63-bit int)

OCaml Approach

OCaml's mod_pow is naturally recursive: if exp = 0 then 1 else if exp mod 2 = 0 then let h = mod_pow base (exp/2) m in h * h mod m else base * mod_pow base (exp-1) m mod m. For tail-recursive efficiency, the accumulator version threads the result: let rec go acc base exp m. OCaml's Int64.mul handles 64-bit products; for moduli requiring 128-bit, Zarith.mpz is used. Matrix exponentiation extends naturally with OCaml's algebraic types for 2x2 or NxN matrices.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Fast Modular Exponentiation in OCaml *)

(* Recursive binary method — elegant and clear *)
let rec pow_mod_rec (base : int) (exp : int) (m : int) : int =
  if exp = 0 then 1 mod m
  else if exp land 1 = 1 then
    (* Odd exponent: a^n = a * a^(n-1) *)
    let rest = pow_mod_rec base (exp - 1) m in
    Int64.(to_int (rem (mul (of_int base) (of_int rest)) (of_int m)))
  else
    (* Even exponent: a^n = (a^(n/2))^2 *)
    let half = pow_mod_rec base (exp / 2) m in
    Int64.(to_int (rem (mul (of_int half) (of_int half)) (of_int m)))

(* Iterative binary method — more efficient (no stack) *)
let pow_mod (base : int) (exp : int) (m : int) : int =
  let result = ref 1 in
  let base = ref (base mod m) in
  let exp = ref exp in
  while !exp > 0 do
    if !exp land 1 = 1 then
      result := Int64.(to_int (rem (mul (of_int !result) (of_int !base)) (of_int m)));
    base := Int64.(to_int (rem (mul (of_int !base) (of_int !base)) (of_int m)));
    exp := !exp lsr 1
  done;
  !result

(* Matrix exponentiation for Fibonacci — shows generality of the method *)
(* M^n via binary exponentiation where M is a 2x2 matrix *)
type matrix = { a: int; b: int; c: int; d: int }

let mat_mul m1 m2 modp =
  let mm a b = Int64.(to_int (rem (mul (of_int a) (of_int b)) (of_int modp))) in
  { a = (mm m1.a m2.a + mm m1.b m2.c) mod modp;
    b = (mm m1.a m2.b + mm m1.b m2.d) mod modp;
    c = (mm m1.c m2.a + mm m1.d m2.c) mod modp;
    d = (mm m1.c m2.b + mm m1.d m2.d) mod modp }

let mat_id = { a=1; b=0; c=0; d=1 }

let rec mat_pow m exp modp =
  if exp = 0 then mat_id
  else if exp land 1 = 1 then mat_mul m (mat_pow m (exp-1) modp) modp
  else let half = mat_pow m (exp/2) modp in mat_mul half half modp

(* F(n) mod p using matrix exponentiation in O(log n) *)
let fib_mod n p =
  if n = 0 then 0
  else
    let m = mat_pow { a=1; b=1; c=1; d=0 } (n-1) p in
    m.a

let () =
  Printf.printf "2^10 mod 1000 = %d  (expected 24)\n" (pow_mod 2 10 1000);
  Printf.printf "3^100 mod 1_000_000_007 = %d\n" (pow_mod 3 100 1_000_000_007);
  Printf.printf "2^1000 mod 1009 = %d\n" (pow_mod 2 1000 1009);
  Printf.printf "recursive: 2^10 mod 1000 = %d\n" (pow_mod_rec 2 10 1000);
  Printf.printf "fib(10) mod 100 = %d  (expected 55)\n" (fib_mod 10 100);
  Printf.printf "fib(100) mod 1_000_000_007 = %d\n" (fib_mod 100 1_000_000_007)

Deep Comparison

OCaml vs Rust: Modular Exponentiation

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement matrix exponentiation to compute the nth Fibonacci number in O(log n) using 2×2 matrix multiplication.

Use mod_pow(a, p-2, p) to compute modular inverse and verify a * a^(p-2) ≡ 1 (mod p) for several values.

Implement the Fermat primality test using mod_pow: test if a^(n-1) ≡ 1 (mod n) for multiple bases a.

Compute 2^(10^18) mod (10^9 + 7) and verify the result using the property 2^p-1 ≡ 1 (mod p) for Mersenne primes.

Generalize to a Ring trait and implement mod_pow generically over any ring (integers, matrices, polynomials).

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust