에라토스테네스 (기원전 276~194) · 오일러 · 리만 · 현재까지

소수 수의 원자

핵심 사실: 1보다 큰 모든 자연수는 소수들의 곱으로 유일하게 표현된다 — 수의 세계를 이루는 원자. 소수가 무한히 많다는 것은 기원전에 증명됐지만, 분포의 패턴은 아직 완전히 이해되지 않았다.

소수란 무엇인가

1보다 크고 1과 자기 자신만을 약수로 갖는 수: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

산술의 기본 정리: 1보다 큰 모든 자연수는 소수의 곱으로 유일하게 표현된다.

$$84 = 2^2 \times 3 \times 7 \qquad 1001 = 7 \times 11 \times 13 \qquad 997 = 997$$

이것이 소수를 "수의 원자"라고 부르는 이유다. 원소 주기율표처럼, 모든 수는 소수 원소들로 분해된다.

소수는 무한히 많다 — 유클리드의 증명 (기원전 300년)

이 증명은 2300년이 지난 지금도 수학 역사상 가장 우아한 증명 중 하나로 꼽힌다.

귀류법 증명:

소수가 유한하다고 가정하자: $p_1, p_2, \ldots, p_n$이 전부라 하자.
$N = p_1 \times p_2 \times \cdots \times p_n + 1$을 만들면
$N$을 $p_1, p_2, \ldots, p_n$ 중 어떤 것으로 나눠도 나머지가 1 → 이 소수들 중 어떤 것도 $N$을 나누지 못한다.
그러면 $N$ 자체가 소수이거나, $N$은 목록에 없는 새로운 소수로 나누어진다. 모순!
따라서 소수는 무한히 많다. ∎

에라토스테네스의 체 — 소수 찾기

기원전 고대 그리스의 알고리즘. N까지의 소수를 찾으려면: 2부터 시작해서 각 소수의 배수들을 모두 지운다. 남은 수들이 소수다.

2부터 200까지 소수 탐색

소수의 분포 — 규칙 없이 규칙적인

소수는 불규칙하게 나타나는 것처럼 보이지만, 전체적으로는 놀랍도록 규칙적인 패턴을 따른다.

소수 계량 함수 $\pi(n)$: n 이하의 소수 개수.

$$\pi(n) \sim \frac{n}{\ln n} \quad \text{(소수 정리, 1896년 Hadamard \& de la Vallée Poussin 증명)}$$

녹색: 실제 π(n). 노란색: 근사 n/ln(n). n이 커질수록 근사가 정확해진다.

울람 나선 — 소수의 신비한 패턴

1963년 수학자 스타니스와프 울람은 회의 중 지루해서 숫자를 나선형으로 배열해 소수에 점을 찍었다. 그런데 소수들이 대각선으로 몰리는 패턴이 보였다. 아직 완전히 설명되지 않은 현상이다.

밝은 점 = 소수. 대각선 방향으로 소수가 몰리는 것이 보이는가?

쌍둥이 소수 — 아직 풀리지 않은 문제

쌍둥이 소수는 차이가 2인 소수 쌍이다: (3,5), (5,7), (11,13), (17,19), (29,31), (41,43), ...

쌍둥이 소수 추측: 쌍둥이 소수는 무한히 많다. 단순해 보이는 이 추측은 아직 미증명이다. 2013년 장이탕(Yitang Zhang)이 "차이가 7,000만 이하인 소수 쌍이 무한히 많다"는 것을 처음 증명했고, 이후 폴리매스 프로젝트가 이를 246까지 줄였다. 하지만 2는 아직 멀었다.

소수와 암호학 — RSA의 원리

현대 인터넷 보안의 기반이 소수에 있다. RSA 암호화의 핵심 아이디어:

단방향 함수의 비대칭성:

쉬운 방향: 두 소수 $p, q$를 곱해서 $n = p \times q$ 계산 → 컴퓨터로 0.001초
어려운 방향: $n$을 보고 $p, q$ 찾기 (소인수분해) → 2048비트 $n$이면 현재 컴퓨터로 우주의 나이보다 긴 시간 필요
공개키 = $n$ (누구나 볼 수 있음), 개인키 = $p, q$ (서버만 알고 있음)

RSA 간단 예시 (소규모)

$p = 61,\; q = 53$ (실제론 수백 자리)
$n = 61 \times 53 = 3233$ (공개키 일부)
$\phi(n) = 60 \times 52 = 3120$
$e = 17$ (공개 지수)
$d = 2753$ (개인 지수, $ed \equiv 1 \pmod{\phi(n)}$)
암호화: $c = m^e \bmod n$
복호화: $m = c^d \bmod n$

현재 사용 크기

RSA-2048: 2048비트 숫자 (약 617자리)
일반 소인수분해 기록: RSA-250 (250자리, 2020년)
RSA-2048 분해 추정: 현재 기술로 수십억 년
양자 컴퓨터(Shor 알고리즘)는 다항시간 분해 가능 → 포스트양자 암호학 연구 중

리만 가설 — 100만 달러짜리 미해결 문제

소수의 분포를 정확히 기술하려면 리만 제타 함수의 영점을 알아야 한다. 리만(1859)은 모든 비자명 영점이 복소 평면에서 $\text{Re}(s) = 1/2$ 직선 위에 있다고 추측했다.

$$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p\text{ 소수}} \frac{1}{1-p^{-s}}$$

이 가설이 증명되면 소수 분포를 훨씬 정밀하게 기술할 수 있다. 현재까지 수조 개의 영점을 계산했고 모두 이 직선 위에 있었지만, 일반적 증명은 160년째 없다. 클레이 밀레니엄 상금 100만 달러의 7문제 중 하나다.

소수를 이해하면 할수록 더 많은 수수께끼가 등장한다. 분포의 불규칙성 속에 숨은 규칙성, 쌍둥이 소수의 무한성, 리만 가설 — 인류가 수천 년간 연구해온 가장 단순한 개념이 아직도 가장 깊은 미스터리를 품고 있다.