Python에서 Modular Multiplicative Inverse 계산하기

1. 순진한 반복 접근 방식을 사용한 모듈러 곱셈 역함수
2. pow() 내장 함수를 사용한 모듈식 곱셈 역함수

두 개의 숫자 a와 m이 있는 경우 a의 모듈식 승법 역수는 모듈로 m 아래에서 다음과 같은 경우 x입니다.

a * x % m = 1

이 경우 곱셈 역수는 a와 m이 상대적으로 소수인 경우, 즉 a와 m의 최대 공약수가 1인 경우에만 존재합니다.

x의 값 범위는 1에서 m-1까지입니다.

순진한 반복 접근 방식을 사용한 모듈러 곱셈 역함수

모듈로 m에서 a의 곱셈 역원을 찾아야 한다고 가정합니다. 모듈로 곱셈 역이 존재하면 그 값의 범위는 1에서 m-1까지입니다. 따라서 우리는 이 범위를 반복하고 모듈로 곱셈 역의 조건을 확인합니다. 범위 내의 임의의 숫자가 조건을 충족하면 그 숫자를 모듈로 곱셈 역수로 가집니다.

def find_mod_inv(a, m):

    for x in range(1, m):
        if (a % m) * (x % m) % m == 1:
            return x
    raise Exception("The modular inverse does not exist.")


a = 13
m = 22

try:
    res = find_mod_inv(a, m)
    print("The required modular inverse is: " + str(res))

except:
    print("The modular inverse does not exist.")

출력:

The required modular inverse is: 17

여기에 a와 m을 입력으로 받아 모듈로 m 아래에 a의 곱셈 역함수를 반환하는 find_mod_inv라는 함수가 있습니다.

숫자 a에 모듈로 m 아래 ​​a의 곱셈 역원이 없으면 예외가 발생합니다.

위의 예에서 모듈로 22에서 13의 모듈식 곱셈 역수는 17입니다.

pow() 내장 함수를 사용한 모듈식 곱셈 역함수

Python의 내장 함수 pow()를 사용하여 숫자의 모듈식 곱셈 역수를 계산할 수도 있습니다.

a = 38
m = 97
res = pow(a, m - 2, m)
print("The required modular inverse is: " + str(res))

출력:

The required modular inverse is: 23

pow() 메서드를 사용하여 모듈로 곱셈 역을 계산하려면 pow() 메서드의 첫 번째 매개변수는 모듈로 역함수를 찾을 숫자이고 두 번째 매개변수는 모듈로에서 2를 뺀 순서입니다. 마지막 매개변수는 모듈로의 차수입니다.

그러나 Python 3.8 이상에서는 두 번째 인수를 -1로 대체할 수 있습니다.

a = 38
m = 97
res = pow(a, -1, m)
print("The required modular inverse is: " + str(res))

산출

The required modular inverse is: 23