galois.poly_gcd¶
- galois.poly_gcd(a, b)¶
Finds the greatest common divisor of two polynomials \(a(x)\) and \(b(x)\) over \(\mathrm{GF}(q)\).
This implementation uses the Extended Euclidean Algorithm.
- Parameters
a (galois.Poly) – A polynomial \(a(x)\) over \(\mathrm{GF}(q)\).
b (galois.Poly) – A polynomial \(b(x)\) over \(\mathrm{GF}(q)\).
- Returns
galois.Poly – Polynomial greatest common divisor of \(a(x)\) and \(b(x)\).
galois.Poly – Polynomial \(x(x)\), such that \(a x + b y = \textrm{gcd}(a, b)\).
galois.Poly – Polynomial \(y(x)\), such that \(a x + b y = \textrm{gcd}(a, b)\).
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)) # a(x) and b(x) only share the root 2 in common In [3]: b = galois.Poly.Roots([1,2], field=GF); b Out[3]: Poly(x^2 + 4x + 2, GF(7)) In [4]: gcd, x, y = galois.poly_gcd(a, b) # 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*x + b*y == gcd Out[6]: True