galois.egcd

galois.egcd(a, b)

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

Parameters

• a (int, galois.Poly) – The first integer or polynomial argument.

• b (int, galois.Poly) – The second integer or polynomial argument.

Returns

• int, galois.Poly – Greatest common divisor of \(a\) and \(b\).

• int, galois.Poly – The multiplicand \(s\) of \(a\), such that \(a s + b t = \mathrm{gcd}(a, b)\).

• int, galois.Poly – The multiplicand \(t\) of \(b\), such that \(a s + b t = \mathrm{gcd}(a, 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

• 20. Moon, “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

Compute the extended GCD of two polynomials.

In [5]: GF = galois.GF(7)

In [6]: p1 = galois.irreducible_poly(7, 1); p1
Out[6]: Poly(x, GF(7))

In [7]: p2 = galois.irreducible_poly(7, 2); p2
Out[7]: Poly(x^2 + 1, GF(7))

In [8]: p3 = galois.irreducible_poly(7, 3); p3
Out[8]: Poly(x^3 + 2, GF(7))

In [9]: a = p1**2 * p2; a
Out[9]: Poly(x^4 + x^2, GF(7))

In [10]: b = p1 * p3; b
Out[10]: Poly(x^4 + 2x, GF(7))

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