galois.euclidean_algorithm

galois.euclidean_algorithm(a, b)

Finds the greatest common divisor of two integers.

Parameters

• a (int) – Any integer.

• b (int) – Any integer.

Returns

Greatest common divisor of \(a\) and \(b\), i.e. \(gcd(a,b)\).

Return type

int

References

• 20. Moon, “Error Correction Coding”, Section 5.2.2: The Euclidean Algorithm and Euclidean Domains, p. 181

• https://en.wikipedia.org/wiki/Euclidean_algorithm

Examples

In [1]: a, b = 2, 13

In [2]: galois.euclidean_algorithm(a, b)
Out[2]: 1