galois.extended_euclidean_algorithm

galois.extended_euclidean_algorithm(a, b)

Implements the Extended Euclidean Algorithm to find the integer multiplicands of a and b, such that a*x + b*y = gcd(a,b).

Parameters

• a (int) – Any integer.

• b (int) – Any integer.

Returns

• int – Integer x, such that a*x + b*y = gcd(a, b).

• int – Integer y, such that a*x + b*y = gcd(a, b).

• int – Greatest common divisor of a and 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