페르마 소정리와 모듈러 연산 알아보기

페르마 소정리(Fermat's Little Theorem)는 소수와 관련된 중요한 정리로, 정수론에서 매우 유용하게 쓰입니다. 특히 암호학과 소수 판별 알고리즘에서 핵심적인 역할을 합니다. 이 정리를 이해하려면 먼저 '모듈러 연산'이라는 개념을 알아야 합니다. 이번 글에서는 모듈러 연산의 기초부터 페르마 소정리의 수학적 의미와 활용까지 차근차근 설명하겠습니다.

모듈러 연산이란?

모듈러 연산(modular arithmetic)은 어떤 수를 특정 수로 나눈 나머지를 구하는 연산입니다. 수식을 통해 다음과 같이 나타낼 수 있습니다.

\[ a \bmod n \]

이는 \(a\)를 \(n\)으로 나눈 나머지를 의미합니다. 예를 들어,

7 ÷ 3 = 몫 2, 나머지 1
따라서 \(7 \bmod 3 = 1\)입니다.

모듈러 연산은 시계산법과 비슷해서, 정해진 범위 안에서 순환하는 특성이 있습니다. 이 때문에 암호학, 난수 생성, 해시 함수 등 다양한 응용에 활용됩니다.

페르마 소정리란?

페르마 소정리(Fermat's Little Theorem)는 다음과 같은 내용입니다.

p가 소수이고, 정수 a가 p와 서로소(공약수가 1뿐)라면 다음이 성립합니다.

\[ a^{p-1} \equiv 1 \pmod{p} \]

이 정리는 소수 판별이나 모듈러 역원(modular inverse) 계산에 매우 유용합니다.

페르마 소정리의 직관적 의미

페르마 소정리는 "소수 p에 대해, 어떤 수 a가 p와 서로소라면, a를 p번 곱했을 때 p로 나눈 나머지는 원래 값과 같다"는 의미입니다.

쉽게 예를 들면, p = 7이고 a = 3일 때 다음이 성립합니다.

\[ 3^6 \equiv 1 \pmod{7} \]

실제로 계산해보면:

\[ 3^6 = 729,\quad 729 \bmod 7 = 1 \]

이처럼 소수 p와 서로소인 수 a에 대해 이러한 관계가 항상 성립하는 것이 페르마 소정리입니다.

페르마 소정리의 수학적 증명 개요

페르마 소정리는 다음과 같은 정수론적 원리에서 출발합니다. 정수 집합 {1, 2, ..., p-1}을 생각해 봅시다. 이 집합의 각 원소를 어떤 서로소 a로 곱한 집합 {a, 2a, 3a, ..., (p-1)a}를 생각하면, 이 집합도 모듈러 p에서 {1, 2, ..., p-1}의 순열(permutation)이 됩니다.

곱한 결과를 전부 곱해 보면:

\[ 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (p-1) \equiv (a \cdot 1) \cdot (a \cdot 2) \cdot \cdots \cdot (a \cdot (p-1)) \pmod{p} \]

이때 좌변과 우변의 값은 서로 같아야 합니다. 즉,

\[ a^{p-1} \cdot (1 \cdot 2 \cdot \cdots \cdot (p-1)) \equiv (1 \cdot 2 \cdot \cdots \cdot (p-1)) \pmod{p} \]

양변을 공통항으로 나누면

\[ a^{p-1} \equiv 1 \pmod{p} \]

이로써 페르마 소정리가 성립함을 보일 수 있습니다.

페르마 소정리의 활용

1. 소수 판별법

어떤 수 n이 소수인지 확인할 때, 임의의 서로소 a에 대해 다음을 확인할 수 있습니다.

\[ a^{n-1} \stackrel{?}{\equiv} 1 \pmod{n} \]

이 관계를 만족하지 않으면, n은 소수가 아닙니다. (페르마 테스트)

2. 모듈러 역원 계산

모듈러 역원이란 다음 관계를 만족하는 수 \(x\)를 의미합니다.

\[ a \cdot x \equiv 1 \pmod{p} \]

페르마 소정리를 활용하면 다음과 같이 역원을 구할 수 있습니다.

\[ x = a^{p-2} \pmod{p} \]

실제 예제 문제

문제: \(p = 7\)일 때, \(a = 3\)의 모듈러 역원을 구해보자.

해결 방법:

\[ x = 3^{7-2} \pmod{7} = 3^5 \pmod{7} \]

계산:

\[ 3^5 = 243,\quad 243 \bmod 7 = 243 \div 7 = 34 \text{...}5 \]

따라서, 모듈러 역원은 \(x = 5\)입니다.

결론

모듈러 연산은 정수론과 암호학에서 매우 중요한 도구이며, 페르마 소정리는 소수와 모듈러 연산을 연결하는 핵심 정리입니다.

페르마 소정리는 소수 판별, 모듈러 역원 계산 등 다양한 분야에서 활용되며, 특히 RSA 암호 알고리즘과 같은 현대 암호학에서도 필수적인 역할을 합니다.

모듈러 연산과 페르마 소정리를 정확히 이해하면, 수학적 사고력뿐 아니라 암호학, 알고리즘 문제 해결에서도 큰 도움이 될 것입니다.