galois.extended_euclidean_algorithm¶
-
galois.
extended_euclidean_algorithm
(a, b)[source]¶ Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = gcd(a,b)\).
- Parameters
- Returns
int – Integer \(x\), such that \(a x + b y = gcd(a, b)\).
int – Integer \(y\), such that \(a x + b y = gcd(a, b)\).
int – Greatest common divisor of \(a\) and \(b\).
References
Moon, “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181
https://en.wikipedia.org/wiki/Euclidean_algorithm#Extended_Euclidean_algorithm
Examples
In [1]: a, b = 2, 13 In [2]: x, y, gcd = galois.extended_euclidean_algorithm(a, b) In [3]: x, y, gcd Out[3]: (-6, 1, 1) In [4]: a*x + b*y == gcd Out[4]: True