galois.poly_gcd

galois.poly_gcd(a, b)

Finds the greatest common divisor of two polynomials \(a(x)\) and \(b(x)\) over \(\mathrm{GF}(p^m)\).

This function implements the 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

Polynomial greatest common divisor of \(a(x)\) and \(b(x)\).

Return type

galois.Poly

References

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 = galois.poly_gcd(a, b); gcd
Out[4]: Poly(x + 5, 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]: GF = galois.GF(7)

In [7]: a = galois.Poly.Roots([2,2,2,3,6], field=GF); a
Out[7]: Poly(x^5 + 6x^4 + x + 3, GF(7))

In [8]: b = galois.Poly.Roots([1,2,2], field=GF); b
Out[8]: 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 [9]: gcd = galois.poly_gcd(a, b); gcd
Out[9]: Poly(x^2 + 3x + 4, GF(7))

# The GCD has only 2 as a root with multiplicity 2
In [10]: gcd.roots(multiplicity=True)
Out[10]: (GF([2], order=7), array([2]))