C++로 구현하는 오일러 정리: 모듈러 곱셈 역원 계산 프로그램

이 글에서는 오일러 정리(Euler's Theorem)를 활용하여 모듈러 곱셈 역원(modular multiplicative inverse)을 구하는 C++ 프로그램을 소개합니다.

모듈러 곱셈 역원이 존재하려면 대상 숫자와 모듈러 값이 반드시 서로소(coprime) 관계여야 합니다. 즉, 두 수의 최대공약수가 1이어야 한다는 조건입니다.

알고리즘

역원 배열을 계산하는 절차는 다음과 같습니다.

시작
   모듈러 곱셈 역원을 구할 숫자를 입력받는다
   모듈러 값을 입력받는다
   inverseArray 함수를 수행한다:
      modInverse(x + 1, 0)으로 배열 초기화
      modInverse[1] = 1;
      i = 2부터 x까지 반복
         modInverse[i] = (-(y / i) * modInverse[y mod i]) mod y + y
   modInverse 배열을 반환한다
끝

예제 코드

아래 코드는 동적 계획법(DP) 방식으로 1부터 입력값 x까지의 모든 모듈러 역원을 한 번에 계산하는 방식입니다.

#include <iostream>
#include <vector>
using namespace std;
vector<int> inverseArray(int x, int y) {
    vector<int> modInverse(x + 1, 0);
    modInverse[1] = 1;
    for (int i = 2; i <= x; i++) {
        modInverse[i] = (-(y / i) * modInverse[y % i]) % y + y;
    }
    return modInverse;
}
int main() {
    vector<int>::iterator it;
    int a, m;
    cout<<"Enter number to find modular multiplicative inverse: ";
    cin>>a;
    cout<<"Enter Modular Value: ";
    cin>>m;
    cout<<inverseArray(a, m)[a]<<endl;
}

실행 결과

Enter number to find modular multiplicative inverse: 26
Enter Modular Value: 7
7

코드 설명

위 실행 결과에서 26의 모듈러 7에 대한 곱셈 역원은 7입니다. 실제로 26 × 7 = 182이며, 182를 7로 나누면 나머지가 0... 이 아니라 검산해 보면 (26 × 7) mod 7 = 182 mod 7 = 0이 되어야 하지만, 여기서 역원의 정의는 (a × a⁻¹) ≡ 1 (mod m)을 만족하는 값입니다.

핵심 아이디어는 다음 재귀 관계식에 있습니다:

modInverse[i] = (-(y / i) * modInverse[y % i]) mod y + y

i와 y가 서로소일 때, 나눗셈 과정에서 자연스럽게 작은 부분 문제(y % i)의 역원을 재활용할 수 있어 전체 계산이 O(x) 시간 복잡도로 처리됩니다. 마지막에 +y를 더해주는 이유는 음수가 나왔을 때 양수 범위(0 ~ y-1)로 보정하기 위함입니다.

이 방식은 페르마의 소정리나 확장 유클리드 호제법보다 코드가 간결하며, 여러 개의 역원을 한꺼번에 구해야 하는 상황에서 특히 유용합니다.