galois.gcd

class galois.gcd(a, b)

Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = \mathrm{gcd}(a, b)\).

This function implements the Extended Euclidean Algorithm.

Parameters

• a (int) – Any integer.

• b (int) – Any integer.

Returns

• int – Greatest common divisor of \(a\) and \(b\).

• int – Integer \(x\), such that \(a x + b y = \mathrm{gcd}(a, b)\).

• int – Integer \(y\), such that \(a x + b y = \mathrm{gcd}(a, b)\).

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#Extended_Euclidean_algorithm

Examples

In [481]: a = 2

In [482]: b = 13

In [483]: gcd, x, y = galois.gcd(a, b)

In [484]: gcd, x, y
Out[484]: (1, -6, 1)

In [485]: a*x + b*y == gcd
Out[485]: True