소수 (Prime Number) 기초
소수는 $1$보다 큰 자연수 중에서 $1$과 자기 자신만을 약수(Divisor)로 가지는 수를 말합니다. 소수는 모든 정수를 구성하는 기본적인 '벽돌'과 같은 역할을 합니다.
1. 소수의 정의와 특징
① 정의
- 소수 (Prime Number): $1$과 자기 자신만을 약수로 가지는 $1$보다 큰 자연수.
- 예시: $2, 3, 5, 7, 11, 13, 17, 19, 23, \dots$
- 합성수 (Composite Number): $1$과 자기 자신 외의 약수를 가지는 $1$보다 큰 자연수.
- 예시: $4, 6, 8, 9, 10, 12, \dots$
- $1$은 소수도, 합성수도 아닙니다. 소수와 합성수를 분류할 때 기준이 되는 수입니다.
② 소수의 가장 중요한 성질: 소인수분해
산술의 기본 정리 (Fundamental Theorem of Arithmetic)에 따르면, 모든 $1$보다 큰 자연수는 오직 하나의 방식으로 소수들의 곱으로 표현될 수 있습니다.
- 예시: $12 = 2 \times 2 \times 3$, $91 = 7 \times 13$
[Image of Prime Factorization Tree]
2. 소수의 중요성
① 정수론의 기본
소수는 정수론의 모든 분야에서 가장 근본적인 역할을 합니다.
② 현대 암호학 (Cryptography)의 핵심
소수는 현대 보안 시스템의 기밀성을 보장하는 핵심입니다.
- RSA 암호화: RSA는 매우 큰 두 개의 소수를 곱하여 공개키를 만듭니다. 이 공개키를 해독하려면 그 두 개의 큰 소수를 찾아내야 하는데(소인수분해), 현재 기술로는 시간이 매우 오래 걸려 사실상 불가능합니다.
- 보안의 원리: 큰 소수를 찾는 것은 쉽지만, 그 소수들의 곱을 다시 소수들로 분해하는 것은 어렵다는 비대칭적 난이도를 이용합니다.
③ 소수의 분포
소수는 무한히 많지만, 그 출현 패턴이 불규칙하고 예측하기 어렵기 때문에 난수 생성이나 암호화 연구에서 중요한 대상이 됩니다.