C++로 모듈러 지수 연산(Modular Exponentiation) 알고리즘 구현하기

모듈러 지수 연산(Modular Exponentiation)은 (base^exp) % mod 형태의 거듭제곱 나머지 값을 효율적으로 계산하는 알고리즘입니다. 이 연산은 RSA와 같은 공개키 암호 시스템의 핵심으로 활용되며, 매 단계마다 모듈러 연산을 적용해 중간값이 커지지 않도록 함으로써 오버플로우 없이 빠른 계산을 가능하게 합니다.

알고리즘

이 알고리즘은 지수를 비트 시프트로 반복해서 2로 나누고, 그때마다 밑을 제곱하는 '거듭 제곱 기법'을 사용합니다. 단순히 밑을 지수만큼 반복 곱하는 방식(O(n))과 달리 O(log n)의 시간 복잡도로 훨씬 빠르게 결과를 얻을 수 있습니다.

Begin
    function modular():
    // 인자: base(밑), exp(지수), mod(모듈러 값)
    // 함수 본문:
        res = 1로 초기화
        while (exp > 0)
            if (exp mod 2 == 1)      // 지수가 홀수인 경우
                res = (res * base) % mod
            exp = exp >> 1           // 지수를 오른쪽으로 1비트 시프트 (2로 나눔)
            base = (base * base) % mod
        return res
End

C++ 코드 예제

#include <iostream>
using namespace std;
long long modular(long long base, long long exp, int mod) {
    long long res = 1;
    while (exp > 0) {
       if (exp % 2 == 1)
          res= (res * base) % mod;
       exp = exp >> 1;
       base = (base * base) % mod;
    }
    return res;
}
int main() {
    long long b, e;
    int mod;
    cout<<"Enter Base : ";
    cin>>b;
    cout<<"Enter Exponent: ";
    cin>>e;
    cout<<"Enter Modular Value: ";
    cin>>mod;
    cout<<modular(b, e , mod);
    return 0;
}

실행 결과

Enter Base : 7
Enter Exponent: 6
Enter Modular Value: 26
25

동작 원리

위 예제는 7⁶ mod 26을 계산하는 과정입니다. 프로그램은 다음 순서로 동작합니다.

• 지수(6)가 짝수이므로 밑을 제곱하고 지수를 절반으로 줄입니다.
• 지수가 홀수가 되는 순간마다 현재 결과(res)에 밑을 곱한 뒤 모듈러 연산을 적용합니다.
• 모든 단계에서 모듈러 연산을 수행하므로 중간값이 mod보다 커지지 않아 오버플로우를 방지할 수 있습니다.

최종적으로 7⁶ = 117,649이고, 117,649 mod 26 = 25가 출력됩니다. 이처럼 모듈러 지수 연산은 암호학뿐 아니라 큰 수의 나머지 연산이 필요한 다양한 문제에서 필수적인 기법입니다.