GCD and Extended Euclidean Algorithm

Cryptography · Axiom Academy

LESSON GCD and Extended Euclidean Algorithm Understanding how to find the greatest common divisor and solve linear Diophantine equations for cryptography Definition: The greatest common divisor (GCD) of two integers a and b is the largest positive integer that divides both numbers without remainder. Let's see the Euclidean algorithm in action with gcd(252, 105): 2. Step-by-Step Euclidean Algorithm Let's trace through gcd(252, 105) step by step, showing the division at each iteration: Step 1: gcd(252, 105) → 252 = 2 × 105 + 42 Step 2: gcd(105, 42) → 105 = 2 × 42 + 21 Step 3: gcd(42, 21) → 42 = 2 × 21 + 0 Complexity: The algorithm runs in O(log(min( a , b ))) time, making it extremely efficient even for very large numbers. 3. Extended Euclidean Algorithm The Extended Euclidean Algorithm doesn't just find the GCD—it also finds integers x and y such that: This is crucial for cryptography because if gcd( a , n ) = 1 (meaning a and n are coprime), then x is the modular inverse of a modulo n . 4. Extended Algorithm: Back-Substitution Let's find x and y where 252 x + 105 y = 21 using back-substitution: Forward (Euclidean): 252 = 2 × 105 + 42 Backward (Substitution): 21 = 105 - 2 × 42 21 = 105 - 2 × (252 - 2 × 105) Verification: (-2) × 252 + 5 × 105 = -504 + 525 = 21 ✓ 5. Application: Finding Modular Inverses The Extended Euclidean Algorithm is the standard method for finding modular inverses, which are essential in RSA cryptography. Example: Find the inverse of 17 modulo 43.

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