소수(수론)

素數 / Prime Number

• 수학 관련 정보

1 개요

1과 자기 자신으로밖에 나누어지지 않는 숫자.

과거에는 '솟수'라고 표현했으나 맞춤법을 고치면서 '소수'로 바뀌었고, 그 덕분에 위의 항목들과 혼동되지 않도록 유의해서 써야 한다. 표준 발음은 [소쑤]로, 위의 항목과 명확히 구분된다. 북한의 문화어로는 '씨수'라고 하며, 한국에서도 용어를 '씨수'로 바꾸자고 주장하는 수학자들이 있다.

소수의 정의는 '1과 자기 자신으로밖에 나누어 떨어지지 않는 1보다 큰 자연수'. 소수가 아닌 수를 합성수(composite number)라고 한다. 쉽게 이해하기 위해 소수를 '약수가 2개인 수'로 정의하기도 한다. 참고로 1은 소수도, 합성수도 아니다.

후술할 소수 나열에선 알기 힘들지만 수가 커질수록 소수들의 빈도는 점점 감소하며, 소수가 없는 아주 긴 구간들의 출현 빈도들이 높아진다. 이쯤 되면 결국 나중엔 소수가 절대 나오지 않게 되는 게 아닌가 하는 추측도 나올 수 있겠지만, 유클리드에 의해 소수는 무한히 많이 있다는 것이 증명되었다. 오일러는 소수의 역수의 합이 발산한다는, 좀 더 강력한 정리를 증명하였다.

유클리드의 증명은 다음과 같다. 귀류법으로 소수가 유한하다고 가정하자. 그럼 그 소수들을 모두 [math]P_1[/math], [math]P_2[/math], [math]P_3[/math], ..., [math]P_n[/math] 으로 나열할 수 있다. 이제 이 소수들을 몽땅 곱하고 1을 더한 수를 a라고 하자. 즉, [math]a = P_1 P_2 \cdots P_n+1[/math]. 이때 a는 n개의 어떠한 소수로도(가정에 의하면, 모든 소수로) 나눠지지 않으므로, a가 새로운 소수이거나, 아니면 [math]P_1[/math], ..., [math]P_n[/math]이 아닌 새로운 소수로 나눠질 수밖에 없어 소수가 n개뿐이라는 가정에 모순이다. 좀 더 자세한 내용은 네이버캐스트에서 다룬 글을 참조할 것.

소수 정리를 통해 큰 수 n 이하의 소수의 개수를 근사적으로 구할 수 있다.

2 이상의 모든 자연수는 한 개 이상의 소수들의 곱으로 유일하게 나타낼 수 있고, 이 유일한 표현을 소인수분해라 한다. 어찌보면 당연해 보이면서도 흥미로운 사실인데, 소수들의 성질만 연구해도 모든 정수의 성질을 알 수 있다는 의미이기 때문. 덕분에 소수는 자연수와 정수의 성질을 연구하는 정수론의 중심 탐구대상이었다.

하지만 소수의 성질을 밝히는 것은 생각보다 매우 어렵다. 많은 수학자들이 위 무한한 소수들의 분포나 규칙성을 밝혀내려고 했지만, 어느 누구도 정답이라고 할 패턴을 밝혀내진 못했다. 현재까지도 소수에 관련된 다음처럼 많은 문제들이 남아서 호기심을 자극한다.

• 골드바흐의 추측

4 이상의 임의의 짝수가 두 소수의 합으로 나타내어질 수 있는가. 약한 버전은 7 이상의 임의의 홀수가 세 소수의 합으로 나타내어질 수 있는가.

• 쌍둥이 소수 문제

차이가 2인 소수들의 쌍이 무한히 많은가.

• 메르센 소수 문제

[math]M_n=2^n-1[/math] 꼴의 소수가 무한히 많은가. 여담으로 사실 n이 소수일 때만 [math]p[/math]가 소수가 될 수 있다.

• 페르마 소수 문제

[math]F_n=2^{2^n}+1[/math] 꼴의 소수가 무한히 많은가. n=1, 2, 3, 4일 경우 소수이므로 페르마는 이를 모두 소수라고 생각했으나, n=5일 경우 [math]F_5=4294967297[/math]은 641로 나누어짐을 오일러가 보였다. 이후 컴퓨터로 계산한 결과 n이 5 이상이면, 40이 넘어서까지도 이러한 수 중에 소수는 발견되지 않았다.

• 소피 제르맹 소수 문제

어떤 소수 [math]p[/math]에 대해서 [math]2p+1[/math]도 소수가 되는 수 [math]p[/math]가 무한한가

비록 수학의 미해결제가 많기는 하지만, 문제는 소수와 관련해서는 대부분의 문제들이 미해결이라는 것이다... 다행히 '약한' 골드바흐의 추측은 2013년에 완전히 증명되었다. 항목 참조.

현대 수학자들은 소수의 분포에 대해서 순수하게 무작위적이라는 가설을 세우고 있다. 소수의 개수는 특정 평균선을 기준으로 변동하는데, 그 변동하는 양에서는 주기성 같은 경향을 더 찾을 수가 없다는 이야기. 어떤 의미에서 이는 소수의 쉬운 패턴을 찾기란 불가능함을 암시한다. 물론 이런 이야기를 하는 수학자 자신들은, 이 믿음의 기초인 리만 가설에서조차 리만이 예견한 수준을 아직도 벗어나지 못하고 있다.

왠지 일본 서브컬처물에서, 극도의 긴장이나 당황한 상태에서 "침착하자, 침착하게 마음을 안정시키고 소수를 세는거다."라는 혼잣말을 하면서 진정을 하는 묘사가 나오는데. 이는 죠죠의 기묘한 모험에서 나온 것, 죠죠 6부 스톤 오션의 등장인물인 엔리코 푸치의 버릇에서 유래된 것. 항목 참고.

일본에서 '모든 소수의 곱은 홀수인가 짝수인가?'가 논란이 된 적 있다. 얼핏 보면 짝수인 2가 들어있어서 짝수일 것 같지만... 모든 소수를 곱한 것은 수가 아닌 발산하는 극한으로 홀수, 짝수 여부를 확인할 수 없다. 참고로 재규격화를 이용해 구한 모든 소수의 곱은 4π²라고 한다.(???)(PDF) 이건 비슷한 예를 들자면 무한등비급수 [math]1+x+x^2+x^3+\cdots = \displaystyle \frac{1}{1-x}[/math]는 원래는 [math]-1 \lt x \lt 1[/math]에서만 성립하는데, 이 제약을 풀어서 1 + 2 + 4 + 8 + ... = -1이라고 하는 것과 비슷하다.

2 10000 이하의 소수

10000 이하의 소수는 총 1229개이다.
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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257 ,263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973

여기 나와있는 예시보다 더 큰 수가 소수인지 판별하고 싶다면 아래 사이트를 이용하면 된다.

• calcuworld 소수 계산기 - 빠르게 계산 가능하지만, 큰수는 처리하지 못함.
• [1] - 울프람알파에 factorization 이란 단어와 함께 숫자를 넣으면 소인수 분해를 해준다. 또는 'is prime?' 이란 문장과 함께 써도 비슷한 결과를 내준다. 'is fucking prime?' 이란 문장을 써도 결과가 나온다

3 소수와 알고리즘, 암호

소수의 문제는 전통적으로 순수수학의 영역에 속했지만, 20세기 후반 암호학과 컴퓨터의 발전으로 현실과 밀접한 관련을 맺는다.

공개열쇠 암호 체계(public-key cryptography)는 '암호화는 쉽지만 해독하기는 어렵다'라는 개념을 도입해 암호체계의 안정성을 높이는데, 이에 적합한 '연산은 쉬운데 역연산은 어려운' 예가 소인수분해인 것이다. 이 소인수분해의 특성을 쓰는 RSA(3번 항목) 암호체계는 아주 큰 소수 p와 q의 곱 pq를 이용해 암호화를 하지만, 해독하려면 p와 q 각각이 필요하다. 예로 다섯 자리 숫자 둘을 곱하는 건 손으로도 금방 하지만, pq = 1,459,160,519 를 알려주고 p와 q의 쌍 (34,583 × 42,193)을 찾으라고 한다면 꽤 삽질이 필요할 것이다. 실제로 RSA에 쓰는 수가 몇백여 자리의 소수들이다.

덕분에 이런 아주 큰 소수를 찾고 그 수가 소수인지 아닌지를 정하는 소수 판정법과, 역시 큰 수를 소인수분해하는 알고리즘이 중요한 이슈로 떠올랐다.

4 소수 판정법 및 소인수분해

어떤 수가 소수임을 판정하기는 어렵다. 가장 간단하게 생각할 수 있는 방법은 2부터 [math]\sqrt n[/math]까지의 소수로 모두 나누어 보는 것이다. 하지만 n이 50여 자리만 되어도 나눗셈을 몇 번 해야 되는지는 상상만 해도 끔찍하다.

1부터 n까지 모든 소수를 찾는 방법으로 고대 그리스의 수학자 에라토스테네스가 만들어 낸 방법이 있는데, 이는 하나의 수가 소수인지 아닌지를 판정하는 것보다는, 일정 범위 내의 소수를 모두 찾아내는 데 이용하는 경우가 많다. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 과정은 아래와 같다.

1. 먼저 1을 지운다.
2. 2부터 시작해서 찾아내고 싶은 범위만큼 자연수를 죽 늘어 놓는다.
3. 먼저 2를 소수로 표시하고 2를 제외한 2의 배수(4, 6, 8, 10, ...)를 모두 소거한다.
4. 그 다음 3을 소수로 표시하고 남아있는 수 중 3을 제외한 3의 배수(9, 15, 21, ...)도 모두 소거한다.
5. 그 다음 수인 4는 2의 배수라서 소거되었으므로 건너뛴다.
6. 그 다음 수인 5를 소수로 표시하고 남아있는 수 중 5를 제외한 5의 배수(25, 35, 55, ...)도 모두 소거한다.
7. 이 과정을 계속 반복한다.

이렇게 하다 보면 어느 정도까지 왔을 때 소수만 남는다. 아래 그림은 에라토스테네스의 체로 1에서 100까지의 수 중 소수를 찾아낸 예이다.
파일:Attachment/Erathosthenes sieve.png
이 그림에서 굵은 수는 소수를 의미한다. 색깔을 입힌 것은 진행 과정을 알 수 있게 하기 위한 것이다.
물론 모든 소수를 찾는다면 사실상 이 방법 뿐이지만, 하나의 소수만을 찾는다면 이건 위에서 말한 [math]\sqrt n[/math] 나눗셈보다도 훨씬 느리니 당연히 꽝이다.

이산수학과 알고리즘이 발전하면서 소수 판정법은 비약적으로 발전하였다. 1976년 발명된 밀러-라빈 판정법은 [math]O \left( { \left( \log{n} \right)^3 } \right) [/math] 내에 소수를 판별할 수 있지만, 무작위 방법을 쓴다. 밀러-라빈 판정법의 원리는 간단히 말하자면 페르마의 소정리를 많은 경우에 만족시키는지 아닌지를 보는 것이다. 페르마의 소정리는 n이 소수일 때 만족하는 식을 주므로, 이 판정을 통과하지 못했다면 바로 n이 합성수임을 알 수 있다. 하지만 어떤 합성수 n이 여러 번의 판정을 우연히 통과할 확률은 시행횟수 k에 따라서 1/4^k 이하로 현격하게 줄어드니(실제로는 이보다 더욱 작다), 이 확률을 무시한다면 실용적으로는 "k번 판정을 통과했으니 소수일 것이다"라고 할 수 있다. 물론 이 어떤 확률 급의 확률에 재수없게 걸려 합성수를 소수라고 판별할 가능성도 있지만.

2006년에 인도의 세 학생 Manindra Agrawal, Neeraj Kayal, Nitin Saxena이 결정론적 방법을 쓰는 AKS 알고리즘을 개발함으로서, 이론적으로 소수판정이 log(n)의 다항 시간안에 풀릴 수 있음을, 즉 P-문제임을 보였다. P-NP 문제 참고. 물론 실용적으로는 훨씬 빠른 밀러-라빈 등을 선호한다.

한편 소인수분해의 문제는 소수 판정과는 다르게, 매우 어렵다. 확률적 해법으로 양보하더라도 log(n)의 다항시간 등으로 나온다는 것은 아직 상상도 할 수 없다. 이 문제가 어려워 어찌 보면 다행인데, 이 문제가 쉽다면 소수 기반 암호 체계의 대부분이 모두 무용지물이라서다.

이 문서의 내용 중 전체 또는 일부는 소수문서에서 가져왔습니다.</div></div>