확장된 유클리드 호제법

extendedEuclid.js

/**
 * 확장된 유클리드 알고리즘
 * http://bbolmin.tistory.com/45
 * s*m + t*n = gcd(m, n) 일때
 * @method extendedEuclid
 * @param  {int}    a   r1
 * @param  {int}    b   r2
 * @return {int}        t1
 */

// s*m + t*n = gcd(a, b)

// a  = b * q1 + r1
// r1 = a + (-1) * q1 * b
// r1 = s1 * a + t1 * b

// s1 = 1
// t1 = (-1) * q1

// ---

// b  = r1 * q2 + r2
// r2 = b + (-1) * r1 * q2
// r2 = b + (-1) * q2 * (s1 * a + t1 * b)
// r2 = b + (-1) * q2 * s1 * a + (-1) * q2 * t1 * b
// r2 = (-1) * q2 * s1 * a + ((-1) * q2 * t1 + 1) * b
// r2 = s2 * a + t2 * b

// s2 = (-1) * q2 * s1
// t2 = (-1) * q2 * t1 + 1

// ---

// r1 = r2 * q3 + r3
// r3 = r1 + (-1) * r2 * q3
// r3 = (s1 * a + t1 * b) + (-1) * q3 * (s2 * a + t2 * b)
// r3 = s1 * a + t1 * b + (-1) * q3 * s2 * a + (-1) * q3 * t2 * b
// r3 = (s1 + (-1) * q3 * s2) * a + (t1 + (-1) * q3 * t2) * b
// r3 = s2 * a + t2 * b

// s3 = s1 + (-1) * q3 * s2
// t3 = t1 + (-1) * q3 * t2

function extendedEuclid(r1, r2){
    if(r2 > r1){
        let tmp = r1;
        r1 = r2;
        r2 = tmp;
    }
    let s1  = 1;
    let s2  = 0;
    let t1  = 0;
    let t2  = 1;
    let tmp = r1;
    let q1 , r3, s3, t3;

    while(r2){
        q1 = Math.floor(r1 / r2);
        r3 = Math.floor(r1 % r2);
        s3 = s1 - q1*s2;
        t3 = t1 - q1*t2;

        r1 = r2;
        r2 = r3;
        s1 = s2;
        s2 = s3;
        t1 = t2;
        t2 = t3;
    }

    if(t1 < 0){
        t1 += tmp;
    }
    return t1;
}