Miller-Rabin Primality Test
밀러-라빈 소수 판별법 (Miller-Rabin Primalirty Test) 은, 주어진 자연수 $n$이 소수인지 판별하는 간단한 방법이다. 모든 소수에 대해서 성립하는 페르마의 소정리가 주어진 $n$에 대해서도 성립할 수 있는지 여부를 보고, $n$이 합성수인지, 아마도 소수일지 판단한다. 소수 $p$가 서로소인 $a$에 대해서 다음이 성립한다는 것이 페르마의 소정리이다. $a^{p-1} \equiv 1 \pmod p$ 이 정리가 주어진 $n$에 대해서 위배되는지를 다음과 같이 판단한다. 이 때, $a=1$인 경우는 항상 성립하므로, $a$는 $2 \leq p$에서 적당히 샘플링하여 진행한다. 먼저 $n$이 2의 배수인 경우, $n=2$인 경우에만 소수인 것은 자명하다. 다음은 $n$이 홀수인 경우이..
PS
2020. 8. 27. 00:04