Modular Multiplicative Inverse

Cryptography · Axiom Academy

LESSON Modular Multiplicative Inverse Understanding multiplicative inverses in modular arithmetic and their critical role in cryptographic systems 1. Definition and When Inverses Exist In other words, when you multiply a by its inverse and take the result modulo n , you get 1. Existence Condition: The inverse a -1 mod n exists if and only if a and n are coprime, meaning: 2. Method 1: Extended Euclidean Algorithm The Extended Euclidean Algorithm is the most general method for finding modular inverses. It not only finds gcd(a, n) but also finds integers x and y such that: When gcd(a, n) = 1, we have a·x + n·y = 1 , which means a·x ≡ 1 (mod n) , so x is our inverse! 3. Method 2: Fermat's Little Theorem (Prime Modulus) When the modulus n is a prime number, we can use Fermat's Little Theorem, which states: Dividing both sides by a (or equivalently, multiplying by a -1 ), we get: This gives us a direct formula for computing inverses when n is prime! 4. Method 3: Euler's Theorem (General Case) For composite moduli, we can use Euler's Theorem, which generalizes Fermat's Little Theorem. For any a with gcd(a, n) = 1: where φ(n) is Euler's totient function (the count of numbers less than n that are coprime to n ). This gives us: 5. Application: RSA Decryption In the RSA cryptosystem, modular multiplicative inverses are essential for key generation. Here's how they're used: Choose e with gcd(e, φ(n)) = 1

This is the written version of the interactive lesson above. See the full Cryptography course.