<b><font size="4">0. 서론</font></b> <div><br></div> <div>어떤 수 n 이 소수인지 아닌지 판정하는 것은 고대 그리스 시절부터 아주 유명한 주제였습니다.</div> <div>오래전 부터 다양한 소수 판정 방법이 연구되었습니다.</div> <div>그 유명한 '에라토스테네스의 체' 부터 시작되는 연구 주제이지요.</div> <div><br></div> <div><div><b><font size="4">1. 루트(n) 보다 작은 소수들로 나눠 보기</font></b></div> <div><br></div> <div>어떤 수 n 이 소수(prime number) 인지 판정하는 가장 쉬운 방법은 루트 n (=√n) 보다 작은 소수들로 모두 나눠 보는 것입니다.</div> <div>간단하게 n=10000+1 이라면 √n < 101 이니깐, 101 보다 작은 소수로 모두 나눠 봐서 나누어 떨어지는지 아닌지 확인하면 됩니다.</div> <div>101보다 작은 소수는 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 로 25개 밖에 안되니깐, <span style="font-size:9pt;">금방 계산할 수 있습니다. 참 쉽죠?</span></div> <div><br></div> <div>n = 10^8 + 1 = 100000001 이라고 하죠. √n < 10001 이니깐, 총 1229개의 소수로 나눠 보면 됩니다. 아직까지는 별 게 아닙니다. 아직까지는 종이와 연필만 가지고도 계산은 해 볼 여지가 있습니다.</div> <div><br></div> <div>n = 10^16 + 1 = 10000000000000001 이면, √n < 100000001 입니다. 1억보다 작은 모든 소수가 필요한데, 슬슬 난이도가 올라 갑니다. 컴퓨터 없이는 엄두가 안나는 레벨이 됩니다.</div> <div><br></div> <div>n = 10^32 + 1 이면, 이제는 모두 몇개의 소수로 나눠 봐야 하는지도 잘 모르는 수준이 됩니다. 이건 컴퓨터가 있다고 해도 답이 잘 안나올 거라 봅니니다. 겨우 <b>1경*1경 밖에 안되는 32자리 작은(?)수</b>에서도 답이 안나옵니다.</div></div> <div><br></div> <div><br></div> <div><div><b><font size="4">2. 페르마의 소정리</font></b></div> <div><br></div> <div>페르마의 소정리 (Fermar's little Theorem) 이라는 것이 있습니다</div> <div><br></div> <div><b>"p가 소수이고, a가 p의 배수가 아니면 a^(p-1) ≡ 1 (mod p) 이다."</b></div> <div><br></div> <div>라는 정리입니다. 이 정리는 소수/합성수 판정을 위한 아주 중요한 정리입니다.</div> <div>이 정리는 고등학교 수준에서 아슬아슬하게 증명이 가능은 한데, 자세히 보고 싶으면 정리된 사이트를 참조하세요.</div> <div><a target="_blank" href="https://namu.wiki/w/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98%20%EC%86%8C%EC%A0%95%EB%A6%AC" target="_blank">https://namu.wiki/w/%ED%8E%98%EB%A5%B4%EB%A7%88%EC%9D%98%20%EC%86%8C%EC%A0%95%EB%A6%AC</a></div> <div><br></div> <div>여튼, 위 정리의 '대우'는 아래와 같습니다. (p 는 n 으로 변경)</div> <div><br></div> <div><b>"어떤 수 n 이 적당한 a 에 대해서 a^(n-1) ≡ 1 (mod n) 이 아니면, n 은 소수가 아니다. 즉 n 은 합성수이다."</b></div> <div><br></div> <div>n = 10^32 + 1 이고 a = 2 라고 할때, 2^(n-1) 은 엄청 큰 수이긴 하지만, 컴퓨터를 이용하면 n 으로 나눈 나머지는 상당히 빠르게 구할 수 있습니다.</div> <div><br></div> <div>참고로 a=2 일때 나머지가 1이라고 해서, 그 수가 소수인것은 아닙니다. '카마이클 수'라는 것이 존재하기 때문에 완벽한 방법은 아니지요.</div> <div>a=2,3,5,7,11 등 계산하기 쉬운 작은 수로 해봐서 모두 판정에 통과하면, 일단 '소수 후보'로 등록해 놓고 보다 엄격한 소수 판정 방법을 사용합니다</div></div> <div><br></div> <div><br></div> <div><div><font size="4"><b>3. 더 강력한 소수 판정 방법</b></font></div> <div><br></div> <div>이쯤 되면 유명한 게 AKS 판정법 같은 것입니다.</div> <div><br></div> <div><a target="_blank" href="https://ko.wikipedia.org/wiki/AKS_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95" target="_blank">https://ko.wikipedia.org/wiki/AKS_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95</a></div></div> <div><br></div> <div>수학적 지식 없으면 뭔 소리인지도 이해가 안되기 시작합니다만, 여튼 기본은 페르마의 소정리 로부터 시작됩니다.</div> <div><br></div> <div><br></div> <div><font size="4"><b>4. 메르센 소수의 경우</b></font></div> <div><br></div> <div>메르센 소수의 경우 뤼카-레메 판정법이라는 것이 존재합니다.</div> <div><a target="_blank" href="https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test" target="_blank">https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test</a></div> <div><br></div> <div>이 판정법은 비교적 쉽고(?), 빠르고, 컴퓨터로 구현하기도 용이합니다.</div> <div>가장 큰 소수가 메르센 소수인 이유는 이 판정법 덕분이라고 보면 됩니다. 물론 어마어마한 컴퓨터 노가다의 산물이기도 하고요.</div> <div><br></div> <div>실제로 GIMPS 사이트를 보면 판정법으로 L-L 을 사용했다고 나오는데 이게 <span style="font-size:9pt;">뤼카-레메(</span><span style="font-size:9pt;">Lucas–Lehmer) 판정법입니다.</span></div> <div><a target="_blank" href="https://www.mersenne.org/primes/" target="_blank">https://www.mersenne.org/primes/</a></div> <div><br></div> <div>이 방법으로 무려 자리수가 2300 만자리나 되는 어마어마하게 큰 소수를 발견할 수 있었죠.</div>