galois.poly_egcd¶
- galois.poly_egcd(a, b)¶
Finds the polynomial multiplicands of \(a(x)\) and \(b(x)\) such that \(a(x)s(x) + b(x)t(x) = \mathrm{gcd}(a(x), b(x))\).
This function implements the Extended Euclidean Algorithm.
- Parameters
a (galois.Poly) – A polynomial \(a(x)\) over \(\mathrm{GF}(p^m)\).
b (galois.Poly) – A polynomial \(b(x)\) over \(\mathrm{GF}(p^m)\).
- Returns
galois.Poly – Polynomial greatest common divisor of \(a(x)\) and \(b(x)\).
galois.Poly – Polynomial \(s(x)\), such that \(a(x)s(x) + b(x)t(x) = \mathrm{gcd}(a(x), b(x))\).
galois.Poly – Polynomial \(t(x)\), such that \(a(x)s(x) + b(x)t(x) = \mathrm{gcd}(a(x), b(x))\).
References
Algorithm 2.221 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf
Examples
In [1]: GF = galois.GF(7) In [2]: a = galois.Poly.Roots([2,2,2,3,6], field=GF); a Out[2]: Poly(x^5 + 6x^4 + x + 3, GF(7)) In [3]: b = galois.Poly.Roots([1,2], field=GF); b Out[3]: Poly(x^2 + 4x + 2, GF(7)) # a(x) and b(x) only share the root 2 in common, therefore their GCD is d(x) = x - 2 = x + 5 In [4]: gcd, s, t = galois.poly_egcd(a, b); gcd, s, t Out[4]: (Poly(x + 5, GF(7)), Poly(5, GF(7)), Poly(2x^3 + 4x^2 + x + 2, GF(7))) # The GCD has only 2 as a root with multiplicity 1 In [5]: gcd.roots(multiplicity=True) Out[5]: (GF([2], order=7), array([1])) In [6]: a*s + b*t == gcd Out[6]: True
In [7]: GF = galois.GF(7) In [8]: a = galois.Poly.Roots([2,2,2,3,6], field=GF); a Out[8]: Poly(x^5 + 6x^4 + x + 3, GF(7)) In [9]: b = galois.Poly.Roots([1,2,2], field=GF); b Out[9]: Poly(x^3 + 2x^2 + x + 3, GF(7)) # a(x) and b(x) only share the root 2 in common (with multiplicity 2), therefore their GCD is d(x) = (x - 2)^2 = x^2 + 3x + 4 In [10]: gcd, s, t = galois.poly_egcd(a, b); gcd, s, t Out[10]: (Poly(x^2 + 3x + 4, GF(7)), Poly(2, GF(7)), Poly(5x^2 + 6x + 4, GF(7))) # The GCD has only 2 as a root with multiplicity 2 In [11]: gcd.roots(multiplicity=True) Out[11]: (GF([2], order=7), array([2])) In [12]: a*s + b*t == gcd Out[12]: True