Algorithms
Mathematical Algorithms
Difficulty: Advanced
Computing a^b mod m for a = 7, b = 10^18, and m = 10^9 + 7 looks impossible: even iterating one multiplication per step would take longer than the age of the universe. Binary exponentiation does it in 60 multiplications, by squaring the...
Mathematical Algorithms
Computing a^b mod m for a = 7, b = 10^18, and m = 10^9 + 7 looks impossible: even iterating one multiplication per step would take longer than the age of the universe. Binary exponentiation does it in 60 multiplications, by squaring the base while halving the exponent. RSA encryption depends on exactly this trick, and so do most modular-arithmetic problems in competitive programming.
Mathematical Algorithms assembles the standard toolkit. You will implement the Sieve of Eratosthenes for primes up to N in O(N log log N), plus the segmented sieve for large ranges. Binary exponentiation handles a^b mod m in O(log b), and the matrix-exponentiation generalization computes Fibonacci or any linear recurrence in O(log n). You will derive the Extended Euclidean algorithm for ax + by = gcd(a, b) and use it for modular inverses, walk through the Chinese Remainder Theorem, compute Euler's totient, apply Fermat's Little Theorem to modular inversion, and run the Miller-Rabin probabilistic primality test.
In Number Theory Fundamentals, you saw GCD, primes, and divisibility. Modular Arithmetic introduced congruences and modular inverses. This lesson turns those facts into algorithms that scale to numbers the problem statement actually asks about.
Next, Computational Geometry turns to algorithmic problems on points, lines, and polygons.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Implement the Sieve of Eratosthenes and explain why its complexity is O(N log log N).
Implement binary exponentiation to compute a^b mod m in O(log b) time.
Use matrix exponentiation to compute the nth Fibonacci number in O(log n).
Implement the Extended Euclidean Algorithm and use it to find modular inverses.
Compute Euler's Totient function and apply Euler's theorem for modular exponentiation.
Why This Matters
01
The Sieve of Eratosthenes generates all primes up to N in O(N log log N) — essential for problems involving prime factorization, divisibility, and number-theoretic computations.
02
Binary exponentiation computes a^b mod m in O(log b) instead of O(b), making it feasible to handle exponents of 10^18 — a requirement in competitive programming and cryptography (RSA).
03
Matrix exponentiation extends fast power to compute linear recurrences (like Fibonacci) in O(log n), turning O(n) DP into O(log n).
04
The Extended Euclidean Algorithm and modular inverse are fundamental to solving modular equations, which appear constantly in combinatorics and competitive programming.
Key Terms
6 terms you'll encounter in this lesson
Sieve of Eratosthenes
An algorithm that finds all prime numbers up to N by iteratively marking multiples of each prime as composite, running in O(N log log N) time.
Binary Exponentiation
A method to compute a^b in O(log b) by repeatedly squaring: if b is even, a^b = (a^(b/2))^2; if b is odd, a^b = a * a^(b-1).
Matrix Exponentiation
Applying binary exponentiation to matrices to compute M^n in O(k^3 log n) for k x k matrices. Used to solve linear recurrences in O(log n).
Extended Euclidean Algorithm
An extension of the Euclidean algorithm that, given a and b, finds integers x and y such that ax + by = gcd(a, b). Used to compute modular inverses.
Modular Inverse
The modular inverse of a modulo m is a number x such that a*x ≡ 1 (mod m). It exists only when gcd(a, m) = 1. Found via Extended Euclidean or Fermat's little theorem.
Euler's Totient Function
phi(n) counts integers from 1 to n that are coprime to n. For prime p, phi(p) = p-1. Used in Euler's theorem: a^phi(n) ≡ 1 (mod n) when gcd(a,n)=1.
Heads Up
Common misconceptions to watch out for
"The sieve starts marking from 2*i for each prime i"
The optimized sieve starts marking from i*i (not 2*i), because all smaller multiples of i have already been marked by smaller primes. This reduces work significantly.
"Binary exponentiation is just repeated squaring"
Repeated squaring computes a^1, a^2, a^4, a^8, ... but binary exponentiation selectively multiplies these powers based on the binary representation of b. Not every squared value is used in the final result.
"Modular inverse always exists"
The modular inverse of a mod m exists only when gcd(a, m) = 1. For example, 2 has no modular inverse mod 4 because 2 and 4 share factor 2.
"Fermat's little theorem works for any modulus"
Fermat's little theorem (a^(p-1) ≡ 1 mod p) only works when p is prime. For composite moduli, use Euler's theorem with the totient function instead.