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

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