Extended Euclidean algorithm (Python)

From LiteratePrograms

Other implementations: C++ | Python

This article describes a Python implementation of Extended Euclidean algorithm.

Algorithm

For u and v, this algorithm finds (u₁,u₂,u₃) such that uu₁ + vu₂ = u₃ = gcd(u,v). We use auxiliary vectors (v₁,v₂,v₃) and (t₁,t₂,t₃) in the algorithm. The following equations always hold throughout the algorithm.

ut₁ + vt₂ = t₃

uu₁ + uu₂ = u₃

uv₁ + uv₂ = v₃

1. (Initialization): ,
2. If v₃ = 0, stop.
3. Otherwise, do the following.
   • (t₁,t₂,t₃) = (u₁,u₂,u₃) − (v₁,v₂,v₃) * q
   • and
   • return to 2.

Source

The algorithm is quite straightforward and it is not difficult to translate the algorithm into a Python source code.

<<eea>>=
def eea(u, v):
	u1 = 1
	u2 = 0
	u3 = u
	v1 = 0
	v2 = 1
	v3 = v
	while v3 != 0:
		q = u3 / v3
		t1 = u1 - q * v1
		t2 = u2 - q * v2
		t3 = u3 - q * v3
		u1 = v1
		u2 = v2
		u3 = v3
		v1 = t1
		v2 = t2
		v3 = t3
	return u1, u2, u3

The test driver is also given.

<<eea.py>>=
eea
if __name__ == "__main__":
	a, b, d = eea(352, 168)
	print a, b, d
	a, b, d = eea(168, 352)
	print a, b, d
	a, b, d = eea(3458, 4864)
	print a, b, d

Execution result

crypto@crypto ~/python
$ python eea.py
-10 21 8
21 -10 8
-45 32 38

• The first test case shows that -10 *352 + 21 * 168 = 8 and 8 is gcd(352, 168).
• The second result means that the order of input numbers has no significant meaning.
• The last result shows that -45 * 3458 + 32 * 4864 = 38 and 38 is gcd(3458, 4864).

Download code