Euclidean Algorithms
Description
Euclidean algorithm and Extended Euclidean algorithm are used to GCD and Bezout’s Identity for the given two numbers. They are useful in cryptography when analysing the strength of RSA keys.
Definitions
GCD
It is one of the basic concept used in Cryptography. As per Wikipedia:
the greatest common divisor (GCD), also known as greatest common factor (GCF), of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted
gcd(x, y). For example, the GCD of 8 and 12 is 4, that is, gcd(8, 12) = 4
Euclidean Algorithm
This algorithm is an efficient way to calculate GCD of given two numbers without doing any multiplication or division. From computing perspective, Addition and subtraction takes fewer CPU cycles than multiplication and division.
The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147
- Implementation in Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/python3
def gcd(a, b):
if a == b:
return a
if a < b:
a, b = b, a
return gcd(b, a-b)
if __name__ == "__main__":
import sys
val1 = int(input('Enter first number: ').strip())
val2 = int(input('Enter second number: ').strip())
print(f"GCD of {val1}, {val2}: {gcd(val1, val2)}")
Bézout’s Identity
Let a and b be integers with greatest common divisor d. Then there exist integers x and y such that ax + by = d. Moreover, the integers of the form az + bt are exactly the multiples of d.
Extended Euclidean Algorithm
This algorithm uses the quotient as a continuation parameter for the next iteration, unlike standard Euclidean algorithm where remainder is used for the next iteration.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def extended_euclidean(a, b):
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_euclidean(b % a, a)
# Update x and y using results of recursive call
x = y1 - (b // a) * x1
y = x1
return gcd, x, y
if __name__ == "__main__":
import sys
val1 = int(input('Enter first number: ').strip())
val2 = int(input('Enter second number: ').strip())
gcd, x, y = extended_euclidean(val1, val2)
print(f"GCD of {val1}, {val2}: {gcd}")
print(f"Bezout's Identity: {val1}*{x} + {val2}*{y} = {gcd}")