Modular Exponentiation

Math for CS · Axiom Academy

In cryptography, we need to compute numbers like or even . Computing these directly is impossible: 2^ 1000 has over 300 digits! Naive Approach vs. Smart Approach Problem: a^b can be astronomically large Take mod n after every multiplication Smart: Keep numbers small with modular arithmetic Encryption: is fast to compute Decryption: is also fast to compute Security: Finding d from e and n requires factoring n , which is hard Scale: Works for 2048-bit numbers, the industry standard Repeated squaring reduces from O(b) to operations Uses binary decomposition of exponent Keeps all intermediate results small using modular arithmetic Essential for making RSA and modern cryptography practical One of the most important algorithms in computer science

This is the written version of the interactive lesson above. See the full Math for CS course.