Algorithm: Extended Greatest Common Divisor (Python) 

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]

1.Proof: (related to "Extended Greatest Common Divisor (Python)")