Extended Euclidean

egcd.js

const egcd = (a, b) => {
    [x, y, _x, _y] = [0, 1, 1, 0];
    while (a !== 0) {

        div = parseInt(b / a),
        mod = b % a;

        nx = x - _x * div,
        ny = y - _y * div;

        b = a,
        a = mod,
        x = _x,
        y = _y,
        _x = nx,
        _y = ny;
    }

    let gcd = b;

    if (gcd !== 1) {
        console.log("Tidak Memiliki invers");
    } else if ((gcd === 1) && x > 0) {
        console.log("Invers " + ny + " mod " + (-nx) + " = " + x)
    } else if ((gcd === 1) && x < 0) {
        console.log("Invers " + (-ny) + " mod " + nx + " = " + (x + nx))
    }

    return [gcd, x, y];
}


const gcd = (a, b) => {
    return (b == 0) ? a : gcd(b, a % b);
}


console.log(egcd(9, 26));

egcd.py

def egcd(number_1, number_2):
    count = 1
    x,y, x_aksen,y_aksen = 0,1, 1,0
    while number_1 != 0:
        division = number_2 // number_1
        modulo = number_2 % number_1
        new_x = x - x_aksen * division
        new_y = y - y_aksen * division
        
        print '------------------------------------------------------------------------'
        print 'Iterasi ke-',count
        print 'division = (',number_2,')/(',number_1,')=',division
        print 'modulo = (',number_2,')%(',number_1,')=',modulo
        print 'new_x = (',x,')-(',x_aksen,')*(',division,')=',new_x
        print 'new_y = (',y,')-(',y_aksen,')*(',division,')=',new_y
        print 'x =',x
        print 'y =',y
                    
        number_2 = number_1
        print '\n\nnumber_2 = ',number_2,' <= number_1'

        number_1 = modulo
        print 'number_1 = ',number_1,' <= modulo'
        
        x = x_aksen
        print 'x = ',x,' <= x_aksen'
        
        x_aksen = new_x
        print 'x_aksen = ',x_aksen,' <= x_new'
        
        y = y_aksen
        print 'y = ',y,' <= y_aksen'
        
        y_aksen = new_y
        print 'y_aksen = ',y_aksen,' <= y_new'

        print '------------------------------------------------------------------------\n'


        count+=1
        
           
    gcd = number_2
    if (gcd!=1):
        print 'Tidak memiliki invers!'
    if (gcd==1) & (x>0):
        print 'Invers',new_y,'modulo',-new_x,'=',x
    if (gcd==1) & (x<0):
        print 'Invers',-new_y,'modulo',new_x,'=',x+new_x
        
    #return gcd, x, y
    print 'Extended Euclidean-nya adalah (',gcd,',',x,',',y,')'
    return 'Perhitungan Sukses!!!'

print 'Mencari Extended Eucledian'
# @interact
# def _(
A = 9
modulus = 26
auto_update=False
# ):
print 'Fungsi egcd(a,b)menghasilkan (gcd,x,y)'
print 'sehingga bisa ditulis gcd = a*x + b*y = GCD(a,b)'
print 'Invers ada jika GCD(',A,',',modulus,') = 1'
print 'GCD(',A,',',modulus,') ='
print egcd(A, modulus)

pseudocode.txt

fungsi extended_gcd(a, b)
    x  = 0
    y  = 1
    x' = 1
    y' = 0

    ketika a bukanlah 0 maka :
        div = b / a 
        mod = b % a
        a_x = (x - x') * div
        a_y = (y - y') * div

        b = a
        a = mod
        x = x'
        y = y'
        x' = a_x
        y' = a_y
   
    gcd = b
    kembalikan [gcd, x, y]

result.txt

Mencari Extended Eucledian
Fungsi egcd(a,b)menghasilkan (gcd,x,y)
sehingga bisa ditulis gcd = a*x + b*y = GCD(a,b)
Invers ada jika GCD( 9 , 26 ) = 1
GCD( 9 , 26 ) =
------------------------------------------------------------------------
Iterasi ke- 1
division = ( 26 )/( 9 )= 2
modulo = ( 26 )%( 9 )= 8
new_x = ( 0 )-( 1 )*( 2 )= -2
new_y = ( 1 )-( 0 )*( 2 )= 1
x = 0
y = 1


number_2 =  9  <= number_1
number_1 =  8  <= modulo
x =  1  <= x_aksen
x_aksen =  -2  <= x_new
y =  0  <= y_aksen
y_aksen =  1  <= y_new
------------------------------------------------------------------------

------------------------------------------------------------------------
Iterasi ke- 2
division = ( 9 )/( 8 )= 1
modulo = ( 9 )%( 8 )= 1
new_x = ( 1 )-( -2 )*( 1 )= 3
new_y = ( 0 )-( 1 )*( 1 )= -1
x = 1
y = 0


number_2 =  8  <= number_1
number_1 =  1  <= modulo
x =  -2  <= x_aksen
x_aksen =  3  <= x_new
y =  1  <= y_aksen
y_aksen =  -1  <= y_new
------------------------------------------------------------------------

------------------------------------------------------------------------
Iterasi ke- 3
division = ( 8 )/( 1 )= 8
modulo = ( 8 )%( 1 )= 0
new_x = ( -2 )-( 3 )*( 8 )= -26
new_y = ( 1 )-( -1 )*( 8 )= 9
x = -2
y = 1


number_2 =  1  <= number_1
number_1 =  0  <= modulo
x =  3  <= x_aksen
x_aksen =  -26  <= x_new
y =  -1  <= y_aksen
y_aksen =  9  <= y_new
------------------------------------------------------------------------

Invers 9 modulo 26 = 3
Extended Euclidean-nya adalah ( 1 , 3 , -1 )
Perhitungan Sukses!!!