galois.gcd¶
- galois.gcd(a, b)¶
Finds the greatest common divisor of \(a\) and \(b\).
- Parameters
a (int, galois.Poly) – The first integer or polynomial argument.
b (int, galois.Poly) – The second integer or polynomial argument.
- Returns
Greatest common divisor of \(a\) and \(b\).
- Return type
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
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))