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