galois.gcd - galois

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 Polynomials

Compute the GCD of two integers.

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

Generate irreducible polynomials over $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))