개념
1과 자기 자신으로만 나뉘는 1보다 큰 자연수. 모든 양의 정수의 소인수 분해를 이루는 곱셈의 원자이며, RSA 같은 일부 공개키 암호에서도 중요한 역할을 한다.
한 호흡으로 이해하기
"1과 자기 자신으로만 나뉘는 1보다 큰 수" — 2, 3, 5, 7, 11, 13, ... 정수 곱셈의 원자. 유클리드는 소수가 무한히 많음을 증명했다. RSA는 큰 합성수의 인수분해가 알려진 고전 알고리즘으로 어렵다는 점을 이용하지만, 인터넷 보안은 여러 암호 방식·프로토콜·구현의 조합이다.
한눈에 보기
처음 25개 소수 |
|---|
2, 3, 5, 7, 11 |
13, 17, 19, 23, 29 |
31, 37, 41, 43, 47 |
53, 59, 61, 67, 71 |
73, 79, 83, 89, 97 |
에라토스테네스의 체로 손쉽게 찾을 수 있는 정수의 원자들.
핵심 식
1과 자기 자신으로만 나뉘는 수
풀이 예제
- 1
Q.6은 소수?
- 2
Q.13은 소수?
핵심 순간
유클리드의 무한성 증명
《원론》 9권 명제 20은 유한한 소수 목록을 가정해도 그 목록 밖의 소수가 필요함을 보인다. 오래된 순수 정수론의 대표적 증명이지만, “최초의 비실용적 정리”처럼 목적을 단정하지는 않는다.
에라토스테네스의 체
알렉산드리아의 에라토스테네스가 소수를 찾는 단순하고 강력한 알고리즘 발견. 오늘날까지 컴퓨터에서 사용되는 패턴.
리만 가설의 등장
리만이 소수 분포가 ζ함수의 영점과 깊이 연결됨을 발견. 오늘날까지 풀리지 않은 백만 달러 밀레니엄 문제.
RSA — 소수가 인터넷을 지킨다
리베스트·샤미르·아델만이 큰 소수와 모듈러 산술을 이용한 공개키 암호를 발표했다. RSA는 널리 쓰였지만 현대 TLS는 타원곡선 방식과 대칭키·해시 등 여러 층을 함께 사용한다.
오늘날의 응용
RSA와 일부 난수·해시 구성, 오류정정과 유한체 계산에 쓰인다. 큰 수의 인수분해가 알려진 고전 알고리즘으로 어렵다는 점은 RSA의 한 전제이며, 인터넷 보안 전체는 다른 수학과 프로토콜에도 의존한다.
MathVoyage 너머로
불러오는 중…