C++로 구현하는 페르마의 소정리(Fermat's Little Theorem)

페르마의 소정리(小定理)는 초등 정수론의 기본 결과 중 하나로, 페르마 소수 판별법(Fermat primality test)의 이론적 기반이 됩니다. 이 정리는 1640년에 이를 언급한 피에르 드 페르마(Pierre de Fermat)의 이름을 따서 명명되었습니다.

정리의 내용은 다음과 같습니다. p가 소수라면, 임의의 정수 a에 대해 a^p − a는 p의 배수가 됩니다. 특히 a와 m이 서로소이고 m이 소수일 때, a의 모듈러 역원(modular inverse)은 a^(m−2) mod m으로 계산할 수 있습니다.

알고리즘

시작
    power() 함수 : 모듈로 M 하에서 a의 b제곱을 계산
    modInverse() 함수 : 모듈로 m에서 a의 모듈러 역원을 계산
        m은 소수라고 가정
        a와 m이 서로소이면,
            모듈러 역원 = a^(m - 2) mod m
끝

예제 코드

#include <iostream>
using namespace std;
int pow(int a, int b, int M) {
    int x = 1, y = a;
    while (b > 0) {
        if (b % 2 == 1) {
            x = (x * y);
            if (x > M)
                x %= M;
        }
        y = (y * y);
        if (y > M)
            y %= M;
        b /= 2;
    }
    return x;
}
int modInverse(int a, int m) {
    return pow(a, m - 2, m);
}
int main() {
    int a, m;
    cout<<"모듈러 곱셈 역원을 구할 수 입력: ";
    cin>>a;
    cout<<"모듈러 값 입력: ";
    cin>>m;
    cout<<modInverse(a, m)<<endl;
}

위 코드의 pow() 함수는 거듭제곱을 빠르게 계산하기 위해 분할 정복 방식(빠른 거듭제곱)을 사용합니다. 지수를 절반씩 줄여가며 계산하므로 시간 복잡도는 O(log b)입니다. modInverse() 함수는 페르마의 소정리를 활용해 a^(m−2) mod m 값을 반환함으로써 모듈러 역원을 구합니다.

실행 결과

모듈러 곱셈 역원을 구할 수 입력: 26
모듈러 값 입력: 7
3

실행 결과를 확인해 보면, 26 × 3 = 78이고 78 mod 7 = 1이므로 26의 모듈로 7에서의 곱셈 역원이 3임을 알 수 있습니다. 이처럼 페르마의 소정리는 모듈러 연산에서 나눗셈을 처리하거나 큰 수의 거듭제곱을 효율적으로 계산할 때 매우 유용하게 활용됩니다.