galois.egcd¶
- galois.egcd(a: int, b: int) Tuple[int, int, int] ¶
- galois.egcd(a: Poly, b: Poly) Tuple[Poly, Poly, Poly]
Finds the multiplicands of \(a\) and \(b\) such that \(a s + b t = \mathrm{gcd}(a, b)\).
- Parameters
- a
The first integer or polynomial argument.
- b
The second integer or polynomial argument.
- Returns
Greatest common divisor of \(a\) and \(b\).
The multiplicand \(s\) of \(a\).
The multiplicand \(t\) of \(b\).
Notes
This function implements the Extended Euclidean Algorithm.
References
Algorithm 2.107 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf
Algorithm 2.221 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf
Moon, T. “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181
Examples
Compute the extended GCD of two integers.
In [1]: a, b = 12, 16 In [2]: gcd, s, t = galois.egcd(a, b) In [3]: gcd, s, t Out[3]: (4, -1, 1) In [4]: a*s + b*t == gcd Out[4]: True
Generate irreducible polynomials over \(\mathrm{GF}(7)\).
In [5]: GF = galois.GF(7) In [6]: f1 = galois.irreducible_poly(7, 1); f1 Out[6]: Poly(x, GF(7)) In [7]: f2 = galois.irreducible_poly(7, 2); f2 Out[7]: Poly(x^2 + 1, GF(7)) In [8]: f3 = galois.irreducible_poly(7, 3); f3 Out[8]: Poly(x^3 + 2, GF(7))
Compute the extended GCD of \(f_1(x)^2 f_2(x)\) and \(f_1(x) f_3(x)\).
In [9]: a = f1**2 * f2 In [10]: b = f1 * f3 In [11]: gcd, s, t = galois.egcd(a, b) In [12]: gcd, s, t Out[12]: (Poly(x, GF(7)), Poly(2x^2 + 4x + 1, GF(7)), Poly(5x^2 + 3x + 4, GF(7))) In [13]: a*s + b*t == gcd Out[13]: True