galois.egcd - galois

galois.egcd(a: int, b: int) → tuple[int, int, int]

galois.egcd(a: Poly, b: Poly) → tuple[galois._polys._poly.Poly, galois._polys._poly.Poly, galois._polys._poly.Poly]

Finds the multiplicands of $a$ and $b$ such that $a s + b t = \gcd (a, b)$ .

Parameters:¶

a: int¶
a: Poly: The first integer or polynomial argument.
b: int¶
b: Poly: The second integer or polynomial argument.

Returns:¶

Greatest common divisor of $a$ and $b$ .
The multiplicand $s$ of $a$ .
The multiplicand $t$ of $b$ .

See also

gcd, lcm, prod

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¶

Integers Polynomials

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 $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