어떤 수 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자리 작은(?)수에서도 답이 안나옵니다.

페르마의 소정리 (Fermar's little Theorem) 이라는 것이 있습니다

라는 정리입니다. 이 정리는 소수/합성수 판정을 위한 아주 중요한 정리입니다.

이 정리는 고등학교 수준에서 아슬아슬하게 증명이 가능은 한데, 자세히 보고 싶으면 정리된 사이트를 참조하세요.

여튼, 위 정리의 '대우'는 아래와 같습니다. (p 는 n 으로 변경)

n = 10^32 + 1 이고 a = 2 라고 할때, 2^(n-1) 은 엄청 큰 수이긴 하지만, 컴퓨터를 이용하면 n 으로 나눈 나머지는 상당히 빠르게 구할 수 있습니다.

참고로 a=2 일때 나머지가 1이라고 해서, 그 수가 소수인것은 아닙니다. '카마이클 수'라는 것이 존재하기 때문에 완벽한 방법은 아니지요.

a=2,3,5,7,11 등 계산하기 쉬운 작은 수로 해봐서 모두 판정에 통과하면, 일단 '소수 후보'로 등록해 놓고 보다 엄격한 소수 판정 방법을 사용합니다

이쯤 되면 유명한 게 AKS 판정법 같은 것입니다.