소수 (수론)

정의
수학의 수론에서 소수(素數, prime number)란 1과 자기 자신 외에는 약수가 존재하지 않는 1보다 큰 자연수를 말한다. 즉, 정수 $p$가 소수일 필요조건은 $p > 1$이며, $p = a \times b$인 두 정수 $a, b$가 존재할 경우 $a = 1$ 또는 $b = 1$ 이어야 함을 의미한다.

예시
가장 작은 소수는 2이며, 2 이후의 소수들은 3, 5, 7, 11, 13, 17, 19, 23, 29 등이다. 2는 유일한 짝수 소수이며, 다른 모든 짝수는 2와 다른 소수의 곱으로 표현될 수 있다.

기본 성질

1. 무한성

   • 유클리드(기원전 300년경)는 모든 소수들의 곱에 1을 더한 수는 기존에 존재하던 소수와 서로 서로소임을 이용해 소수가 무한히 존재한다는 증명을 제시하였다.

2. 기본정리(산술의 기본정리)

   • 모든 자연수는 소수들의 곱으로 유일하게 표현된다(순서와 소수의 중복을 제외하고). 이는 소수들이 정수론에서 “빌딩 블록” 역할을 함을 나타낸다.

3. 소수 판정

   • 소수 여부를 판정하기 위한 알고리즘으로는 에라토스테네스의 체, Miller–Rabin 시험, AKS 소수 판정법 등이 있다. 현대 암호학에서는 특히 큰 소수를 효율적으로 생성하고 검증하는 방법이 중요하다.

4. 분포

   • 소수의 밀도는 정수 직선 상에서 점차 감소한다. 소수정리(Prime Number Theorem, 19세기 말)에서는 $x$ 이하의 소수 개수를 $\pi(x)$라 할 때 $\displaystyle \pi(x) \sim \frac{x}{\log x}$ 임을 보였다. 이는 $x$가 커짐에 따라 소수 사이의 평균 간격이 대략 $\log x$에 비례한다는 의미이다.

역사적 배경
소수 개념은 고대 그리스 수학자들, 특히 에우클리드와 피타고라스학파에서 이미 다루어졌다. 유클리드의 《원론》(Elements)에서 소수와 합성수의 개념이 체계적으로 정리되었으며, 이후 중세·근대 수학자들이 소수의 분포와 판정 방법을 탐구하였다. 19세기에는 리만(Riemann)이 제시한 리만 가설이 소수의 미세한 분포와 깊은 연관성을 제시함으로써 현대 수론 연구의 핵심 문제 중 하나가 되었다.

응용

• 암호학
  RSA, Diffie–Hellman, Elliptic Curve Cryptography 등 현대 공개키 암호 체계는 큰 소수(수백 자리 이상의 소수)와 그에 관련된 연산의 어려움에 기반한다. 소수의 난수 생성과 검증은 안전한 키 생성에 필수적이다.

• 해시 함수 및 난수 생성
  소수를 이용한 모듈러 연산은 난수 생성기와 해시 알고리즘에서 주기성을 제어하는 데 활용된다.

• 수학적 모델링
  소수열은 복잡계, 신호 처리, 물리학 등 다양한 분야에서 패턴 분석과 모델링에 사용된다.

관련 개념

참고

• 유클리드, 《원론》
• 갈로드, 《소수정리》(1796)
• 리만, “ζ(s) 함수와 소수분포” (1859)
• 아담스, 베스, “AKS 소수판정법” (2002)

위 내용은 수학·수론 분야에서 널리 인정받는 사실에 기반한 객관적 서술이며, 현재까지 학계에서 검증된 정보이다.