GCD & EGCD

Euclids Algorithm

Note :

a%b = a - (a//b)*b

a.x ≡ 1 (mod m)
x ≡ 1/a (mod m)
x ≡ a^(-1) (mod m)

GCD

Source code : (python)

def gcd(a, b): 
    print(a, b)
    if a == 0 :
        return b 
      
    return gcd(b%a, a)

a = 210
b = 118

print(gcd(a,b))

output

210 118
118 210
92 118
26 92
14 26
12 14
2 12
0 2
2

Penjelasan

a                  b       210 118
b%a                a       118 210
a%(b%a)           b%a       92 118
(b%a)%(a%(b%a))  a%(b%a)   ...
...

iter       a       b       x   y
0         b%a      a 
1        b0%a0     a0
2        b1%a1     a1
3        b2%a2     a2
...

EGCD

a.x + b.y = GCD(a, b)

def egcd(a, b):
    print(a, b)
    if a == 0 :
        print('------')
        print(a, b, '0', '1')
        return b, 0, 1 
    gcd, x1, y1 = egcd(b%a, a) 
    x = y1 - (b//a) * x1 
    y = x1 
    print(a, b, x, y)
    return gcd, x, y
print('(gcd, x, y) :',egcd(a,b))

output

210 118
118 210
92 118
26 92
14 26
12 14
2 12
0 2
------
0 2 0 1
2 12 1 0
12 14 -1 1
14 26 2 -1
26 92 -7 2
92 118 9 -7
118 210 -16 9
210 118 9 -16
(gcd, x, y) : (2, 9, -16)

Penjelasan

iter     a   b   x   y
 0       0   2   0   1
 1       2  12   1   0
 2      12  14  -1   1
 3      14  26   2  -1
 4      26  92  -7   2
 5      92 118   9  -7
 6     118 210 -16   9
 7     210 118   9 -16

karena nilai y merupakan nilai x sebelumnya, maka tinggal mencari nilai x

X(n) = Y(n-1) - (A(n)//B(n))*X(n-1)
Y(n) = X(n-1)