Python에서 Modular Multiplicative Inverse 계산하기

Suraj Joshi 2023년1월30일
  1. 순진한 반복 접근 방식을 사용한 모듈러 곱셈 역함수
  2. pow() 내장 함수를 사용한 모듈식 곱셈 역함수
Python에서 Modular Multiplicative Inverse 계산하기

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

a * x % m = 1

이 경우 곱셈 역수는 am이 상대적으로 소수인 경우, 즉 am의 최대 공약수가 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

여기에 am을 입력으로 받아 모듈로 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
작가: Suraj Joshi
Suraj Joshi avatar Suraj Joshi avatar

Suraj Joshi is a backend software engineer at Matrice.ai.

LinkedIn

관련 문장 - Python Math