# galois.egcd¶

galois.egcd(a, b)

Finds the multiplicands of $$a$$ and $$b$$ such that $$a s + b t = \mathrm{gcd}(a, b)$$.

Parameters
Returns

• int, galois.Poly – Greatest common divisor of $$a$$ and $$b$$.

• int, galois.Poly – The multiplicand $$s$$ of $$a$$, such that $$a s + b t = \mathrm{gcd}(a, b)$$.

• int, galois.Poly – The multiplicand $$t$$ of $$b$$, such that $$a s + b t = \mathrm{gcd}(a, b)$$.

Notes

This function implements the Extended Euclidean Algorithm.

References

Examples

Compute the extended GCD of two integers.

In : a, b = 12, 16

In : gcd, s, t = galois.egcd(a, b)

In : gcd, s, t
Out: (4, -1, 1)

In : a*s + b*t == gcd
Out: True


Compute the extended GCD of two polynomials.

In : GF = galois.GF(7)

In : p1 = galois.irreducible_poly(7, 1); p1
Out: Poly(x, GF(7))

In : p2 = galois.irreducible_poly(7, 2); p2
Out: Poly(x^2 + 1, GF(7))

In : p3 = galois.irreducible_poly(7, 3); p3
Out: Poly(x^3 + 2, GF(7))

In : a = p1**2 * p2; a
Out: Poly(x^4 + x^2, GF(7))

In : b = p1 * p3; b
Out: Poly(x^4 + 2x, GF(7))

In : gcd, s, t = galois.egcd(a, b)

In : gcd, s, t
Out: (Poly(x, GF(7)), Poly(2x^2 + 4x + 1, GF(7)), Poly(5x^2 + 3x + 4, GF(7)))

In : a*s + b*t == gcd
Out: True