galois.gcd¶

galois.gcd(a: int, b: int) → int¶

galois.gcd(a: Poly, b: Poly) → Poly

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

Parameters

a: int¶

a: Poly

The first integer or polynomial argument.

b: int¶

b: Poly

The second integer or polynomial argument.

Returns

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

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]: f1 = galois.irreducible_poly(7, 1); f1
Out[3]: Poly(x, GF(7))

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

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

Compute the GCD of \(f_1(x)^2 f_2(x)\) and \(f_1(x) f_3(x)\), which is \(f_1(x)\).

In [6]: galois.gcd(f1**2 * f2, f1 * f3)
Out[6]: Poly(x, GF(7))