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)

[8187] **Blömer, J.**: “Lecture Notes Algorithmen in der Zahlentheorie”, Goethe University Frankfurt, 1997

[1357] **Hermann, D.**: “Algorithmen Arbeitsbuch”, Addison-Wesley Publishing Company, 1992

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint

© 2018 Powered by BooOfProofs, All rights reserved.

© 2018 Powered by BooOfProofs, All rights reserved.