Welcome guest
You're not logged in.
193 users online, thereof 0 logged in

Extended Greatest Common Divisor (Python)

Known time/storage complexity and/or correctness

Let $$a,b\in\mathbb{Z}$$ be positive integers $a,b\in\mathbb Z$ with $$a\le b$$. The algorithm $$\operatorname{gcdext}(a,b)$$ calculates correctly the greatest common divisor $d$ of $$a$$ and $$b$$ and integers $x,y\in\mathbb Z$ $x,y\in\mathbb Z$ such that $$d=ax+by.$$ It requires $$\mathcal O(\log |b|)$$ (worst case and average case) division operations, which corresponds to $$\mathcal O(\log^2 |b|)$$ bit operations.

Short Name

$\operatorname{gcdext}$

Input Parameters

$a,b\in\mathbb{Z}$

Output Parameters

$d,x,y\in\mathbb Z$

Python Code

def gcdext(a, b):
if a ≤ 0:
NotPositiveException(a)
if b ≤ 0:
NotPositiveException(b)
x = 0
y = 1
u = 1
v = 0
q = a // b
r = a % b
while r != 0:
a = b
b = r
t = u
u = x
x = t - q * x
t = v
v = y
y = t - q * y
if b != 0:
q = a // b
r = a % b
d = b
return [d, x, y]

# Usage
print(gcdext(5159, 4823))

# will output
# [7, -244, 261], which means 7=-244*5159+261*4823

| | | | created: 2019-06-22 05:21:02 | modified: 2019-07-15 09:24:07 | by: bookofproofs | references: [1357], [8187]

(none)