11. 열한 번째 수업: 페르마의 소정리 (Fermat’s Little Theorem)

페르마는 아마추어처럼 낙서를 끄적이는 괴짜였지만, 그의 두뇌에서 튀어나온 정리들은 $350$년이 지난 지금, 전 지구인들의 은행 비밀번호를 지키는 최강의 방패가 되었습니다. 그가 남긴 수많은 업적 중 현대 암호학의 절대적인 성배(Holy Grail)로 불리는 ‘페르마의 소정리(Fermat’s Little Theorem)’를 파헤쳐봅시다.

학습 목표

  • 현대 이산수학과 암호학의 뼈대가 되는 방정식인 페르마의 소정리 공식의 논리를 이해합니다.
  • 엄청난 크기의 거듭제곱 연산을 했을 때 모듈러(나머지)가 어떻게 $1$로 회귀하게 되는지의 마법을 체험합니다.
  • 파이썬의 기적 같은 내장 함수 pow(a, b, mod) 를 통해 슈퍼컴퓨터급 모듈러 거듭제곱(Modular Exponentiation)을 구현해 봅니다.

1. 페르마의 작은 폭탄: 소정리 방정식

페르마가 아주 작은 체구의 ‘소수(Prime)’ $p$를 하나 골랐습니다. 예를 들어 $p = 5$ 입니다. 그리고 아무 ‘정수’ $a$나 하나 골랐습니다. 소수인 $5$의 배수만 아니면 아무 수나 상관없습니다. $a = 2$ 로 해봅시다.

페르마는 $a$를 무려 $p-1$ 번이나 무식하게 거듭제곱 곱하기를 한 다음, 그것을 다시 소수 $p$로 나누어 버리는 장난을 쳤습니다.

$a^{p-1} \pmod p$

  • $a = 2, p = 5$ 이고, 지수 $p-1$은 $4$가 됩니다.
  • $2$를 4번 거듭제곱합니다: $2^4 = \mathbf{16}$
  • 그 $16$을 소수 $5$로 나눕니다: $16 \div 5 = 3$ … 나머지 1

어떤 숫자를 넣든, 소수 $p$의 배수막을 피하기만 한다면 최종 나눗셈의 찌꺼기(나머지)는 수학적 모순 없이 무조건, 완벽하게 ‘1’로 돌아옵니다!

페르마의 소정리 (Fermat’s Little Theorem)

$p$가 소수이고, $a$가 $p$의 배수가 아닌 정수일 때, $a^{p-1} \equiv 1 \pmod p$ ($a$의 $p-1$ 제곱을 $p$로 나누면 나머지는 무조건 1이다.)

이 사소해 보이는 “도착지는 무조건 눈금 1이다” 라는 규칙 하나 때문에, 은행가들은 수천 자리 숫자를 계산기에 넣지 않고도 나눗셈의 결과(나머지)를 미리 암호 열쇠로 설계할 수 있게 되었습니다.

2. Python의 암호학 터보 엔진: pow() 함수

그런데 저 공식에 들어가는 숫자가 $a=2, p=5$ 정도면 귀엽지만, 실제 암호학에서 쓰는 소수 $p$는 수백만 단위입니다. $2^{999999}$ 같이 무식한 제곱을 컴퓨터로 계산시키면 메모리가 폭주해서 오류가 나거나 수만 년이 걸릴 것입니다. 거대한 자릿수 폭발을 막기 위해 파이썬은 이 페르마의 이론을 위해 만들어진 ‘모듈러 지수 연산(Modular Exponentiation)’ 로직을 스킬(pow())로 탑재해 놓았습니다.

# 일반 파이썬 계산기 vs 페르마가 탑재된 모듈러 계산기

a = 3        # 아무 평범한 변수
p = 1000003  # 거대 소수 방패(Prime) 

# 목표 지수: p - 1
exponent = p - 1

print(f"[실험]: {a} 의 {exponent} 거듭제곱을 한 후, 다시 {p} 로 나눈 나머지는?")

# 이 공식을 멍청하게 (3 ** 1000002) % 1000003 으로 치면
# 3을 백만 번 곱하다 파이썬 램(RAM)이 죽여달라고 소리칩니다.

# 하지만 파이썬의 [모듈러 고속 거듭제곱 (pow)] 터보 엔진을 켜면?
# pow(숫자, 지수, 나눌 값)
result = pow(a, exponent, p)

print("=" * 40)
print(f"✅ 연산 소요 시간 0.001초 미만. 최종 나머지 값: {result}")
print("수학자 페르마 만세! 나머지는 언제나 '1'입니다!")

놀랍게도 파이썬의 pow(a, b, p) 함수는 숫자가 비대하게 커지지 않도록 중간중간 알아서 $p$로 계속 잘라내며 곱하는 ‘분할 정복’ 암호학 로직으로 짜증나게 큰 연산을 산술的に 압축시켜버립니다. 이것이 페르마의 소정리가 컴퓨터 공학의 암호 해독 프로그래머들에게 가장 사랑받는 이유이자 RSA 암호 생성기의 가장 핵심적인 심장 엔진입니다.

학습 정리

  1. 페르마의 소정리: 강력한 소수 $p$의 장막 안에서 어떤 수 $a$를 $p-1$ 번 거듭제곱한 뒤 $p$로 다시 나누면 그 나머지는 무조건 $1$이 된다는 모듈러(나머지) 정수론의 위대한 법칙.
  2. 수천만 권의 책을 쌓아 올린 크기의 무식한 거듭제곱 연산일지라도, 페르마의 정리를 알면 결과를 예측하고 통제할 수 있다.
  3. 파이썬의 핵심 내장 함수 pow(a, b, m) 은 단순히 제곱하는 기능이 아니라 거대한 수의 팽창을 막으면서 고속으로 암호 나머지를 판독해 내는 모듈러 연산의 종결자(Terminator)이다.
서브목차