galois.gcd

galois.gcd(a, b)

Finds the greatest common divisor of \(a\) and \(b\).

Parameters
Returns

Greatest common divisor of \(a\) and \(b\).

Return type

int, galois.Poly

Notes

This function implements the Euclidean Algorithm.

References

Examples

Compute the GCD of two integers.

In [1]: galois.gcd(12, 16)
Out[1]: 4

Compute the GCD of two polynomials.

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

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

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

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

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

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

In [8]: gcd = galois.gcd(a, b); gcd
Out[8]: Poly(x, GF(7))