05. 정수론 (Number Theory)

1. 모듈러 연산 (Modular Arithmetic)

시계의 12시간 체계처럼, 어떤 수를 나누었을 때의 '나머지'를 중심으로 연산하는 방법론입니다.

두 정수 \( a, b \) 와 양의 정수 \( n \) 에 대하여, \( a - b \) 가 \( n \) 의 배수일 때 두 수는 모듈로 \( n \) 에 대해 합동(Congruent)이라고 하며 다음과 같이 표기합니다.

$$ a \equiv b \pmod{n} $$

• 덧셈: \( (a + b) \pmod n = ((a \pmod n) + (b \pmod n)) \pmod n \)
• 곱셈: \( (a \times b) \pmod n = ((a \pmod n) \times (b \pmod n)) \pmod n \)

모듈러 연산은 무한히 커질 수 있는 수를 유한한 크기의 공간(Finite Field/Ring)에 가두기 때문에 암호학 연산에서 컴퓨터 오버플로우를 막아줍니다.

[Wikipedia: Modular Arithmetic]

2. 유클리드 호제법 (Euclidean Algorithm)

두 정수 \( a \) 와 \( b \) 의 최대공약수(GCD: Greatest Common Divisor)를 빠르게 구하는 알고리즘입니다. 암호학에서 두 수가 서로소(GCD가 1)인지 판별하는 것은 공개키 생성 시 매우 중요합니다.

핵심 원리는 다음과 같습니다. \( a = b \times q + r \) 일 때,

$$ \gcd(a, b) = \gcd(b, r) $$

Interactive: 유클리드 호제법 시뮬레이터

예를 들어, \( \gcd(48, 18) \) 을 구하는 과정을 아래 애니메이션으로 확인해 보세요. 앞선 단계의 나누는 수(\( b \))가 다음 단계의 나뉠 수(\( a \))가 되고, 나머지(\( r \))가 나누는 수가 됩니다.

[Wikipedia: Euclidean Algorithm]

3. 확장 유클리드 호제법 (Extended Euclidean Algorithm)

단순히 최대공약수를 구하는 것을 넘어, 베주 항등식(Bézout's identity)을 만족하는 두 정수 \( x, y \) 를 찾는 방법입니다.

$$ a \cdot x + b \cdot y = \gcd(a, b) $$

이 방법은 암호학에서 모듈러 역원(Modular Multiplicative Inverse)을 찾을 때 필수적으로 사용됩니다. (예: RSA 암호에서 비밀키 \( d \) 를 계산할 때)

4. 오일러 파이 함수 (Euler's Totient Function)

\( n \) 보다 작고 \( n \) 과 서로소인 양의 정수의 개수를 나타내는 함수 \( \phi(n) \) 입니다.

• \( p \) 가 소수(Prime)일 때: \( \phi(p) = p - 1 \)
• \( p, q \) 가 서로 다른 소수일 때: \( \phi(pq) = \phi(p)\phi(q) = (p-1)(q-1) \)

이 성질이 바로 RSA 암호의 안전성을 보장하는 핵심 수학적 트릭입니다.

5. 오일러의 정리 (Euler's Theorem)

페르마의 소정리(Fermat's Little Theorem)를 일반화한 정리입니다. \( a \) 와 \( n \) 이 서로소일 때, 다음이 성립합니다.

$$ a^{\phi(n)} \equiv 1 \pmod{n} $$

이 정리를 응용하면 아주 큰 지수의 모듈러 연산을 극적으로 단순화할 수 있어, 거듭제곱을 사용하는 공개키 암호(비대칭키) 알고리즘을 가능하게 만듭니다.