galois.gcd¶

galois.gcd(a, b)¶

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

Parameters¶

a : int or galois.Poly¶

The first integer or polynomial argument.

b : int or galois.Poly¶

The second integer or polynomial argument.

Returns¶

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

Return type¶

int or galois.Poly

See also

egcd, lcm, prod

Notes

This function implements the Euclidean Algorithm.

References

• Algorithm 2.104 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf

• Algorithm 2.218 from https://cacr.uwaterloo.ca/hac/about/chap2.pdf

Examples

Integers

Compute the GCD of two integers.

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

Polynomials

Generate irreducible polynomials over \(\mathrm{GF}(7)\).

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))

Compute the GCD of two polynomials.

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))