"Extended Euclidean algorithm"의 두 판 사이의 차이

2017년 8월 11일 (금) 16:02 판

python code is as follows,

def exteuclid(m, n, s0=1, s1=0, t0=0, t1=1): 
    # s0 := s_{i-1}
    # s1 := s_i
    # t0 := t_{i-1}
    # t1 := t_i
    assert m>=n
    q = m/n
    r = m%n
    s = s0 - q*s1
    t = t0 - q*t1
    if r==0:
        return n, s1, t1
    else:
        return exteuclid(n, r, s1, s, t1, t)
#test
#print exteuclid(240, 46)
#(2, -9, 47)

as you can notice, this uses recursion, but the wiki’s pseudo code does not.

Modular multiplicative inverse는 다음으로 구한다.

def invmult(a, n):
    if a<n:
        a += n
    r, x, _ = exteuclid(a, n)
    # caution: if r>1, `a` is not invertible.
    if x<0:
        x += n
    return x
#test
#print invmult(234242, 11117) #coprime
#10154

ref. coprime test

@@ 21번째 줄: / 21번째 줄: @@
 #(2, -9, 47)
      </pre>
+as you can notice, this uses recursion, but the [https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm wiki]’s pseudo code does not.
 [https://en.m.wikipedia.org/wiki/Modular_multiplicative_inverse Modular multiplicative inverse]는 다음으로 구한다.