꽤나 큰 $N$이 소수 인지를 판별할 때 쓰는 방법입니다.
$2$부터 $\sqrt{N}$까지 나누어보는 방법 은 상당히 느리므로 밀러-라빈 소수판별법 을 기초로 합니다.
밀러-라빈 소수판별법은 입력된 수가 홀수일 때 깔끔하게 작동하니 $2$를 제외한 짝수는 미리 걸러주도록 합니다.
또, $N$이 정말 랜덤한 큰 수 라는 가정 하에 $2$, $3$, $5$...의 배수가 아닐 확률은 크지 않습니다.
예를 들어, $2$의 배수가 아닐 확률은 $\frac{1}{2}$, $3$의 배수가 아닐 확률은 $\frac{2}{3}$, $5$의 배수가 아닐 확률은 $\frac{4}{5}$...인데, 이를 $\frac{40}{41}$까지 다 곱해보면 $\frac{19110297600}{131710070791} = 0.145093670..$이 되는데, 이미 이 과정에서 소수 판별 대상이 대략 $\frac{1}{7}$로 줄어든 것입니다.
또, 페르마의 소정리 와 파이썬의 파이썬 pow 함수 를 이용해 pow(2, N - 1, N) != 1인지 확인하여 (즉, $2^{N - 1} \not\equiv 1 \pmod{N}$인지 확인) 기타 합성수들을 한번에 걸러줍니다.
이미 이 과정에서 거의 대부분의 합성수들은 날아가고 남은 판별 대상은 진짜 소수들과 유사소수인 Poulet Number 밖에 남지 않습니다.
Poulet Number는 생각보다 많지 않기 때문에, 이 과정에서 대부분의 합성수는 날아갑니다.
풀렛 수들은 밀러-라빈 소수판별법으로 날려주되, 그 전에 발전된 프로트의 정리 를 사용해줍니다.
$N$이 프로트수인지 판별해주고, $d \not\equiv 0 \pmod{3}$이면 $3^{\frac{N - 1}{2}} \equiv -1 \pmod{N}$인지만 판단해도 충분합니다.
$N$이 $2^{64}$ 이하로 입력될 것이 확실한 상황에서는 import math를 할 필요는 없습니다.
강한 뤼카 수열 소수판별법 등을 이용하여 베일리-PSW 소수판별법을 구현해보는 방식도 생각하고 있습니다.