Euclid's Algorithm
Understanding the Basics,
Applications, and Implementation
Introduction
• Euclid's Algorithm is an efficient method for
computing the greatest common divisor (GCD)
of two numbers. It is one of the oldest known
algorithms, introduced by the Greek
mathematician Euclid.
Algorithm Overview
• 1. Divide the larger number by the smaller
number.
• 2. Take the remainder.
• 3. Replace the larger number with the smaller
number and the smaller number with the
remainder.
• 4. Repeat until the remainder is zero.
• 5. The last non-zero remainder is the GCD.
Key Features
• 1. Simple and efficient.
• 2. Works for both integers and polynomials.
• 3. Basis for modern cryptographic algorithms.
• 4. Can be extended to find solutions to linear
Diophantine equations.
Flowchart (Text Representation)
• 1. Start
• 2. Input two numbers a and b.
• 3. Repeat until b equals 0:
• a. Compute r = a % b.
• b. Set a = b and b = r.
• 4. Output a (GCD) as the result.
• 5. End
Pseudocode
• function gcd(a, b):
• while b ≠ 0:
• r=a%b
• a=b
• b=r
• return a
Python Implementation
• def gcd(a, b):
• while b != 0:
• a, b = b, a % b
• return a
• # Example Usage
• print(gcd(56, 98)) # Output: 14
Example 1: Finding GCD
• Find the GCD of 56 and 98:
• 1. 98 % 56 = 42
• 2. 56 % 42 = 14
• 3. 42 % 14 = 0
• GCD = 14
Applications
• 1. Simplifying fractions.
• 2. Cryptography (e.g., RSA algorithm).
• 3. Solving linear Diophantine equations.
• 4. Finding least common multiples (LCM).
Extended Euclid's Algorithm
• The extended version not only computes the
GCD but also finds integers x and y such that:
• a * x + b * y = gcd(a, b)
Implementation of Extended
Algorithm
• def extended_gcd(a, b):
• if b == 0:
• return a, 1, 0
• gcd, x1, y1 = extended_gcd(b, a % b)
• x = y1
• y = x1 - (a // b) * y1
• return gcd, x, y
Complexity Analysis
• Time Complexity:
• - O(log(min(a, b))).
• Space Complexity:
• - O(1) for iterative.
• - O(log(min(a, b))) for recursive.
Real-world Use Case
• In cryptography, Euclid's Algorithm is used in
the RSA encryption algorithm to compute the
private key by finding the modular
multiplicative inverse.
Advantages and Limitations
• Advantages:
• - Efficient and straightforward.
• - Wide applicability.
• Limitations:
• - Does not work with negative inputs directly.
• - Requires iterative or recursive steps.
Conclusion
• Euclid's Algorithm is a timeless mathematical
tool with significant practical applications. Its
simplicity and efficiency make it invaluable in
computer science and mathematics.