◀ ▲ ▶Branches / Theoretical-computer-science / Semi-numerical-algorithms / Algorithm: Extended Greatest Common Divisor (Python)

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.

Algorithm: Extended Greatest Common Divisor (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def gcdext(a, b):
    if a <= 0:
        raise TypeError("a <= 0")
    if b <= 0:
        raise TypeError("b <= 0")
    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], because 7 = -244*5159 + 261*4823

Table of Contents

Proofs: 1

Mentioned in:

Proofs: 1
Propositions: 2 3

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Hermann, D.: "Algorithmen Arbeitsbuch", Addison-Wesley Publishing Company, 1992
2. Blömer, J.: "Lecture Notes Algorithmen in der Zahlentheorie", Goethe University Frankfurt, 1997