코드노예

모듈로 연산에서 역수는 다음과 같습니다.

두 정수 a와 m 에 대해서, a의 m에 대한 모듈러 역수 x는 a에 x를 곱해서 m으로 나눈 나머지가 1이 되는 값을 찾으면 됩니다. 이 때 x는 m보다 작은 양의 정수 입니다.

 a * x ~= 1 (mod m)

x는 a와 m이 서로 소인 경우 반드시 존재합니다.

예를 들어, a = 3, m = 11 이라면, x는 4가 됩니다.

(3 * 4) % 11 = 1

위의 예제에서 x = 4라는 값을 찾기 위해서는 x 에 순차적으로 1부터 대입해 보면 구할 수 있지만, 시간이 많이 걸리기 때문에 다음의 방법으로 더 효율적으로 구할 수 있습니다. 

개선을 위해서 a와 m이 서로 소인 경우, 유클리드 호제법을 이용한 방법을 소개합니다.

정수 a와 b가 주어졌을 때, 각각 x, y를 곱해서 최대공약수와 x, y를 찾습니다.

a * x + b * y = gcd(a, b)

a의 m에 대한 모듈러 역수를 찾기 위해서, b를 m이라 놓고, a와 m은 서로 소이기 때문에 최대공약수를 1로 설정합니다.

a * x + m * y = 1

양변을 m으로 나눈 나머지를 취하면,

a * x + m * y ~= 1 (mod m)
a * x ~= 1 (mod m)

x는 a의 m에 대한 모듈러 역수가 됩니다.

유클리드 호제법을 이용하여 모듈러 역수를 구하는 것을 python으로 구현한 코드는 다음과 같습니다.

def modInverse(a, m):
    m0 = m
    y = 0
    x = 1
    
    if (m == 1):
        return 0
    
    while (a > 1):
        q = a // m
        
        t = m
        
        m = a % m
        a = t
        t = y
        
        y = x - q * y
        x = t
        
    if (x < 0):
        x = x + m0
    
    return x

만약 m이 소수라면, 페르마의 소정리를 이용할 수 도 있습니다.

a ^ (m-1) ~= 1 (mod m)
a ^ (-1) ~= a ^ (m-2) (mod m)

페르마의 소정리 양변에 a ^ (-1) 을 곱하고, 좌변과 우변을 바꾸면, 우리가 찾는 모듈러 역수는 a ^ (m-2) 를 m으로 나눈 나머지가 됩니다.

기존에 사용했던 gcd 코드를 재활용해서 구현한 python 코드 입니다.

def modInverse(a, m):
    g = gdc(a, m)
    if (g != 1):
        # Inverse doesn't exist
        return -1
    else:
        return pow(a, m - 2, m)

def gcd(x, y):   
    while(y): 
        x, y = y, x % y   
    return x

정리를 해보면, a와 m이 서로 소이고, m이 소수라면 페르마의 소정리를 이용해서, 아래식으로 구하는 것이 가장 효율적이고,

a ^ (m-2) % m

m이 소수는 아니지만, a와 m이 서로 소라면 유클리드 호제법을 이용

유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나입니다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘입니다.

재귀호출을 통해서 구하는 방법과 반복문을 통해서 구하는 방법이 있습니다.

재귀호출을 이용하는 방법입니다.

def gcd(m,n):
        if m < n:
                m, n = n, m
        if n == 0:
                return m
        if m % n == 0:
                return n
        else:
                return gcd(n, m%n)

반복문을 이용하는 방법입니다.

def gcd(x, y):   
        while(y): 
                x, y = y, x % y   
        return x 

라메의 정리에 의하면, 최대공약수를 구할 때, 소인수 분해를 이용하는 것 보다 유클리드 호제법을 이용하여 구하는 것이 훨씬 빠른 것으로 알려져있습니다.