소수 계산기

소수의 모든 것: 수학의 기본 원리부터 암호학까지 (2025)

소수의 정의와 역사

소수(Prime Number)는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다. 가장 작은 소수는 2이며 유일한 짝수 소수입니다. 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 이렇게 계속됩니다. 고대 그리스 수학자 유클리드는 기원전 300년경 "소수는 무한히 많다"는 것을 증명했습니다. 소수는 수학에서 매우 중요한 역할을 하며 "수의 원자(atoms of numbers)"라고 불립니다. 산술의 기본정리(Fundamental Theorem of Arithmetic)에 따르면 1보다 큰 모든 자연수는 소수들의 곱으로 유일하게 표현됩니다. 예를 들어 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5입니다. 이것은 마치 모든 물질이 원자로 이루어진 것처럼, 모든 수가 소수로 이루어져 있음을 의미합니다.

소수 판별 알고리즘

어떤 수 n이 소수인지 판별하는 가장 단순한 방법은 2부터 n-1까지 모든 수로 나누어보는 것이지만, 이는 매우 비효율적입니다. 개선된 방법은 2부터 √n까지만 확인하는 것입니다. 왜냐하면 n = a × b일 때 a ≤ √n 또는 b ≤ √n이 반드시 성립하기 때문입니다. 예를 들어 101이 소수인지 확인하려면 √101 ≈ 10.05이므로 2, 3, 5, 7만 확인하면 됩니다. 더 효율적인 밀러-라빈(Miller-Rabin) 확률적 소수 판별법은 매우 큰 수도 빠르게 판별할 수 있습니다. AKS 소수 판별법은 2002년에 발견된 최초의 다항 시간 결정적 알고리즘입니다. 현대 암호학에서는 수백 자리의 소수를 다루기 때문에 효율적인 소수 판별이 매우 중요합니다.

에라토스테네스의 체: 소수 생성 알고리즘

에라토스테네스의 체(Sieve of Eratosthenes)는 기원전 240년경 그리스 수학자 에라토스테네스가 개발한 소수 찾기 알고리즘입니다. 방법은 다음과 같습니다: ① 2부터 n까지의 모든 수를 나열합니다. ② 2는 소수이므로 표시하고, 2의 배수(4, 6, 8, 10...)를 모두 지웁니다. ③ 다음 지워지지 않은 수 3은 소수이므로 표시하고, 3의 배수(6, 9, 12, 15...)를 모두 지웁니다. ④ 다음 지워지지 않은 수 5는 소수이므로 표시하고, 5의 배수를 모두 지웁니다. ⑤ 이 과정을 √n까지 반복합니다. ⑥ 남은 모든 수가 소수입니다. 예를 들어 30까지의 소수를 찾으면: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29입니다. 이 알고리즘의 시간 복잡도는 O(n log log n)으로 매우 효율적입니다. 100만 이하의 모든 소수를 몇 초 안에 찾을 수 있습니다.

소인수분해의 원리와 응용

소인수분해(Prime Factorization)는 어떤 수를 소수들의 곱으로 나타내는 것입니다. 산술의 기본정리에 따라 1보다 큰 모든 자연수는 유일한 소인수분해를 가집니다. 소인수분해 방법: ① 가장 작은 소수 2부터 시작하여 나누어떨어지는지 확인합니다. ② 나누어떨어지면 계속 2로 나눕니다. ③ 더 이상 2로 나누어지지 않으면 다음 소수 3, 5, 7...로 시도합니다. ④ 몫이 1이 될 때까지 반복합니다. 예: 360을 소인수분해하면 360 ÷ 2 = 180, 180 ÷ 2 = 90, 90 ÷ 2 = 45, 45 ÷ 3 = 15, 15 ÷ 3 = 5, 5 ÷ 5 = 1. 따라서 360 = 2³ × 3² × 5입니다. 소인수분해의 활용: 최대공약수와 최소공배수 계산, 분수 약분, RSA 암호화의 안전성 기반. 큰 수의 소인수분해가 어렵다는 점이 현대 암호학의 핵심입니다.

쌍둥이 소수와 골드바흐 추측

쌍둥이 소수(Twin Primes)는 차이가 2인 소수 쌍입니다. (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)... 등이 있습니다. 쌍둥이 소수 추측(Twin Prime Conjecture)은 "무한히 많은 쌍둥이 소수가 존재한다"는 주장인데, 아직 증명되지 않은 수학의 미해결 문제 중 하나입니다. 2013년 장이탕(Yitang Zhang)은 차이가 7000만 이하인 소수 쌍이 무한히 많다는 것을 증명했고, 이후 협력 연구를 통해 이 간격을 246까지 줄였습니다. 골드바흐 추측(Goldbach Conjecture)은 "2보다 큰 모든 짝수는 두 소수의 합으로 표현할 수 있다"는 주장입니다. 예: 4=2+2, 6=3+3, 8=3+5, 10=3+7=5+5, 100=3+97=11+89. 1742년 제시되었지만 여전히 증명되지 않았습니다. 컴퓨터로 4×10¹⁸까지 검증되었습니다.

RSA 암호화와 소수의 실용적 응용

RSA 암호화는 인터넷 보안의 핵심 기술로, 큰 소수의 곱셈은 쉽지만 소인수분해는 어렵다는 수학적 성질을 이용합니다. RSA 키 생성 과정: ① 두 개의 큰 소수 p, q를 선택합니다(각각 1024비트 이상). ② n = p × q를 계산합니다(공개키의 일부). ③ φ(n) = (p-1)(q-1)을 계산합니다. ④ φ(n)과 서로소인 공개지수 e를 선택합니다(보통 65537). ⑤ e × d ≡ 1 (mod φ(n))을 만족하는 비밀지수 d를 계산합니다. 공개키는 (n, e), 비밀키는 (n, d)입니다. 암호화: C = M^e mod n, 복호화: M = C^d mod n. n을 소인수분해하여 p와 q를 알아내면 비밀키 d를 계산할 수 있지만, 수백 자리 수의 소인수분해는 현재 컴퓨터로도 실질적으로 불가능합니다(수백만 년 소요). 소수의 다른 응용: 해시 테이블 크기를 소수로 설정하면 충돌 감소, 매미의 13년·17년 생명주기는 포식자와 주기가 겹치지 않도록 진화, 음악의 리듬 패턴에서 소수 박자 사용.