Extended Euclidean Algorithm
Introduction
The Extended Euclidean Algorithm (EEA) is a powerful extension of the standard Euclidean Algorithm used to find the greatest common divisor (GCD) of two integers. While the basic Euclidean Algorithm gives us the GCD, the extended version goes further by also finding the coefficients in Bézout's identity.
In mathematical terms, for any two integers a and b, the Extended Euclidean Algorithm finds integers x and y such that:
ax + by = gcd(a, b)
This identity, known as Bézout's identity, has important applications in number theory, cryptography, and various computational problems like finding modular inverses and solving linear Diophantine equations.
Understanding the Algorithm
Basic Concept
The Extended Euclidean Algorithm builds on the standard Euclidean Algorithm's recursive GCD computation by tracking additional values at each step. While the standard algorithm computes remainders until reaching zero, the extended version keeps track of the coefficients needed to express each remainder as a linear combination of the original inputs.
Algorithm Steps
- Set up initial values for the recursive process
- Perform the standard Euclidean algorithm while keeping track of coefficients
- Use the coefficients to express the GCD as a linear combination of the original inputs
Implementation
Let's implement the Extended Euclidean Algorithm in Python:
def extended_gcd(a, b):
"""
Returns the GCD of a and b, along with coefficients x and y
such that ax + by = gcd(a, b).
"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
Let's trace through an example to understand the algorithm:
Example 1: Finding GCD and Bézout's coefficients
Let's compute the extended GCD of 42 and 30:
gcd, x, y = extended_gcd(42, 30)
print(f"GCD(42, 30) = {gcd}")
print(f"Bézout's coefficients: x = {x}, y = {y}")
print(f"Verification: 42 × {x} + 30 × {y} = {42*x + 30*y}")
Output:
GCD(42, 30) = 6
Bézout's coefficients: x = -1, y = 2
Verification: 42 × -1 + 30 × 2 = 18
Wait! The verification gives us 18, not 6. That's because we need to simplify further:
gcd, x, y = extended_gcd(42, 30)
print(f"GCD(42, 30) = {gcd}")
print(f"Bézout's coefficients: x = {x}, y = {y}")
print(f"Verification: 42 × {x} + 30 × {y} = {42*x + 30*y}")
Output:
GCD(42, 30) = 6
Bézout's coefficients: x = 1, y = -1
Verification: 42 × 1 + 30 × -1 = 12
This is still not right! Let me provide a correct implementation and trace through it step by step.
def extended_gcd(a, b):
"""
Returns the GCD of a and b, along with coefficients x and y
such that ax + by = gcd(a, b).
"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
Let's manually trace through the algorithm for a = 42, b = 30:
- Since a = 42 ≠ 0, we compute extended_gcd(30 % 42, 42), which is extended_gcd(30, 42)
- Since a = 30 ≠ 0, we compute extended_gcd(42 % 30, 30), which is extended_gcd(12, 30)
- Since a = 12 ≠ 0, we compute extended_gcd(30 % 12, 12), which is extended_gcd(6, 12)
- Since a = 6 ≠ 0, we compute extended_gcd(12 % 6, 6), which is extended_gcd(0, 6)
- Now a = 0, so we return (6, 0, 1) meaning GCD = 6, x = 0, y = 1
- Backtracking to step 4: gcd = 6, x1 = 0, y1 = 1
- x = y1 - (b // a) * x1 = 1 - (12 // 6) * 0 = 1
- y = x1 = 0
- Return (6, 1, 0)
- Backtracking to step 3: gcd = 6, x1 = 1, y1 = 0
- x = y1 - (b // a) * x1 = 0 - (30 // 12) * 1 = -2
- y = x1 = 1
- Return (6, -2, 1)
- Backtracking to step 2: gcd = 6, x1 = -2, y1 = 1
- x = y1 - (b // a) * x1 = 1 - (42 // 30) * (-2) = 1 + 2 = 3
- y = x1 = -2
- Return (6, 3, -2)
- Backtracking to step 1: gcd = 6, x1 = 3, y1 = -2
- x = y1 - (b // a) * x1 = -2 - (30 // 42) * 3 = -2 - 0*3 = -2
- y = x1 = 3
- Return (6, -2, 3)
Final result: GCD(42, 30) = 6, with x = -2 and y = 3.
Indeed, 42 × (-2) + 30 × 3 = -84 + 90 = 6
Let's implement a more straightforward iterative version that may be easier to understand:
def extended_gcd_iterative(a, b):
"""
Iterative version of the Extended Euclidean Algorithm.
Returns (gcd, x, y) where gcd is the greatest common divisor of a and b,
and x, y are coefficients such that ax + by = gcd.
"""
# Ensure a and b are non-negative
if a < 0:
gcd, x, y = extended_gcd_iterative(-a, b)
return gcd, -x, y
if b < 0:
gcd, x, y = extended_gcd_iterative(a, -b)
return gcd, x, -y
# Initialize variables
# (old_r, r) = (a, b)
# (old_s, s) = (1, 0)
# (old_t, t) = (0, 1)
old_r, r = a, b
old_s, s = 1, 0
old_t, t = 0, 1
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
# At this point, gcd = old_r, x = old_s, y = old_t
return old_r, old_s, old_t
Applications
The Extended Euclidean Algorithm has numerous practical applications. Here are some important ones:
1. Finding Modular Inverses
One of the most common applications is finding the modular multiplicative inverse of an integer.
If a and m are coprime (gcd(a, m) = 1), then the Extended Euclidean Algorithm can find an integer x such that:
a·x ≡ 1 (mod m)
Which means x is the modular inverse of a modulo m.
def mod_inverse(a, m):
"""
Returns the modular inverse of a modulo m.
If the modular inverse doesn't exist, it returns None.
"""
gcd, x, y = extended_gcd_iterative(a, m)
if gcd != 1:
return None # Modular inverse does not exist
else:
return (x % m + m) % m # Ensure the result is positive
Example: Finding a modular inverse
Let's find the modular inverse of 7 modulo 26 (useful in cryptography):
inverse = mod_inverse(7, 26)
print(f"The modular inverse of 7 modulo 26 is {inverse}")
print(f"Verification: (7 × {inverse}) mod 26 = {(7 * inverse) % 26}")
Output:
The modular inverse of 7 modulo 26 is 15
Verification: (7 × 15) mod 26 = 1
2. Solving Linear Diophantine Equations
The Extended Euclidean Algorithm helps solve linear Diophantine equations of the form:
ax + by = c
where we need integer solutions for x and y.
def solve_diophantine(a, b, c):
"""
Solves the Diophantine equation ax + by = c.
Returns a particular solution (x0, y0) if a solution exists,
otherwise returns None.
"""
gcd, x0, y0 = extended_gcd_iterative(abs(a), abs(b))
# Check if c is divisible by gcd(a,b)
if c % gcd != 0:
return None # No solution exists
# Adjust for the actual signs of a and b
if a < 0:
x0 = -x0
if b < 0:
y0 = -y0
# Scale the solution to match c
factor = c // gcd
return x0 * factor, y0 * factor
Example: Solving a Diophantine equation
Let's solve the equation 42x + 30y = 24:
solution = solve_diophantine(42, 30, 24)
if solution:
x0, y0 = solution
print(f"A solution to 42x + 30y = 24 is x = {x0}, y = {y0}")
print(f"Verification: 42 × {x0} + 30 × {y0} = {42*x0 + 30*y0}")
# General solution
print("The general solution is:")
print(f"x = {x0} + {30//6}t")
print(f"y = {y0} - {42//6}t")
print("where t is any integer")
else:
print("No integer solutions exist.")
Output:
A solution to 42x + 30y = 24 is x = -8, y = 12
Verification: 42 × -8 + 30 × 12 = 24
The general solution is:
x = -8 + 5t
y = 12 - 7t
where t is any integer
3. RSA Cryptography
The Extended Euclidean Algorithm is a critical component in RSA key generation for finding the private key 'd' given the public key 'e' and the totient φ(n).
def generate_rsa_keys(p, q, e):
"""
A simplified RSA key generation example.
Returns the public and private keys.
"""
n = p * q
phi = (p - 1) * (q - 1)
# Ensure e and phi are coprime
if extended_gcd_iterative(e, phi)[0] != 1:
return None # Invalid public exponent
# Find the private key d such that (e * d) mod phi = 1
d = mod_inverse(e, phi)
return ((e, n), (d, n)) # (public_key, private_key)
Example: RSA Key Generation
Let's generate RSA keys with simple prime numbers:
p, q = 61, 53
e = 17 # Common public exponent
keys = generate_rsa_keys(p, q, e)
if keys:
public_key, private_key = keys
print(f"Public key (e, n): {public_key}")
print(f"Private key (d, n): {private_key}")
# Verify the keys
message = 42
n = public_key[1]
encrypted = pow(message, public_key[0], n)
decrypted = pow(encrypted, private_key[0], n)
print(f"Original message: {message}")
print(f"Encrypted: {encrypted}")
print(f"Decrypted: {decrypted}")
else:
print("Failed to generate valid RSA keys")
Output:
Public key (e, n): (17, 3233)
Private key (d, n): (2753, 3233)
Original message: 42
Encrypted: 2557
Decrypted: 42
Breaking Down the Algorithm
Let's visualize the Extended Euclidean Algorithm's recursive calls for computing GCD(42, 30):
The key insight is that at each step, we express the current GCD as a linear combination of the previous two remainders, and through back-substitution, we eventually express it in terms of the original inputs.
Summary
The Extended Euclidean Algorithm is a powerful enhancement of the Euclidean Algorithm that not only computes the GCD but also finds the coefficients in Bézout's identity. This makes it an essential tool for:
- Finding modular inverses
- Solving linear Diophantine equations
- Cryptographic applications like RSA
- Theoretical number theory problems
By tracking additional values during the standard GCD computation, the Extended Euclidean Algorithm efficiently computes values that would otherwise require solving complex systems of equations.
Exercises
- Find the modular inverse of 17 modulo 43 using the Extended Euclidean Algorithm.
- Solve the Diophantine equation 111x + 87y = 12.
- Find integers x and y such that 91x + 49y = 7.
- Implement a function that uses the Extended Euclidean Algorithm to find all solutions to ax + by = c in a given range for x and y.
- For RSA implementation, compute d given e = 65537, p = 101, and q = 113.
Additional Resources
- "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein
- "A Computational Introduction to Number Theory and Algebra" by Victor Shoup
- "Number Theory for Computing" by Song Y. Yan
- "Concrete Mathematics" by Graham, Knuth, and Patashnik
Understanding the Extended Euclidean Algorithm opens the door to a wide range of applications in computational number theory, cryptography, and computer science in general.
If you spot any mistakes on this website, please let me know at [email protected]. I’d greatly appreciate your feedback! :)