Extended Euclidean algorithm
From Elliptic Curve Crypto
The objective of the extended Euclidean algorithm is to compute the greatest common divisor of two natural numbers and solve Bézout’s identity
- .
Given two positive integers a and b, this Diophantine equation is solved for integers x, y, which will not both be positive, and .
If , the algorithm yields the modular inverses[1] of a mod b and b mod a since in this case the congruences
and
are solved. Here is a naïve C++ implementation of pseudocode found on Wikipedia.
#include <iostream>
#include <cassert>
int main(int argc, char **argv) {
long int a, b, q, r0, r1, r,
s0 = 1, s1, s = 0, t0 = 0, t1, t = 1;
std::cout << "Enter two positive integers: ";
std::cin >> a >> b;
assert(a > 0 && b > 0); r0=a; r=b;
while(r != 0) {
q = r0 / r;
r1 = r0 - q * r; r0 = r; r = r1;
s1 = s0 - q * s; s0 = s; s = s1;
t1 = t0 - q * t; t0 = t; t = t1;
}
std::cout
<< "Bézout coefficients: "
<< s0 << ", " << t0 << std::endl
<< "greatest common divisor: "
<< r0 << std::endl
<< "quotients by the gcd: "
<< t << ", "<< s << std::endl;
return 0;
}
- ↑ Bufalo, Michele, Daniele Bufalo, and Giuseppe Orlando. “A Note on the Computation of the Modular Inverse for Cryptography” Axioms, vol. 10, no. 2(116), 2021. https://www.mdpi.com/2075-1680/10/2/116