galois.egcd¶
- galois.egcd(a, b)¶
Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = \mathrm{gcd}(a, b)\).
This function implements the Extended Euclidean Algorithm.
- Parameters
- Returns
int – Greatest common divisor of \(a\) and \(b\).
int – Integer \(x\), such that \(a x + b y = \mathrm{gcd}(a, b)\).
int – Integer \(y\), such that \(a x + b y = \mathrm{gcd}(a, b)\).
References
Moon, “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181
Algorithm 2.107 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf
Examples
In [1]: a = 12 In [2]: b = 28 In [3]: gcd, x, y = galois.egcd(a, b) In [4]: gcd, x, y Out[4]: (4, -2, 1) In [5]: a*x + b*y == gcd Out[5]: True