Miller-Rabin Permality 테스트는 고전적인 방법으로 Fermat 테스트와 Fermat 근 테스트를 결합하여 강력한 유사 소수를 찾습니다. 이 테스트에서 n – 1은 홀수 m과 2의 거듭제곱의 곱으로 쓸 수 있습니다.
$$\mathrm{n-1=m\, x\, 2^{k}}$$
기본 a의 페르마 테스트는 다음과 같이 구성할 수 있습니다.
$$\mathrm{a^{n-1}\, =\, a^{m\, x\, 2k}=\left [ a^{m} \right ]^{2k}=\left [ a^ {m} \right ]\frac{2^{2}\cdot \cdot \cdot 2}{K\, times}}$$
즉, n−1 을 계산하는 것보다 (mod n) 한 단계에서 k+1단계로 수행할 수 있습니다. k + 1을 사용하는 이점은 제곱근 단계의 각 단계를 구현할 수 있다는 것입니다. 제곱근 테스트가 실패하면 중지하고 n을 합성수로 선언할 수 있습니다.
각 단계에서 접근 가능한 경우(결과가 1인 경우) 인접 단계의 모든 그룹에서 페르마 테스트가 통과되고 제곱근 테스트가 충족됨을 제공할 수 있습니다.
초기화
-
밑수 a를 선택하고 $\mathrm{T\, =\, a^{m}}$를 계산할 수 있습니다. 여기서 $\mathrm{m\, =\, \frac{n-1}{2^{k }}}$
-
T가 + 1 또는 -1이면 n이 강력한 의사 소수임을 선언하고 중지합니다. T가 +-1이면 T는 다음 단계에서 1이 되고 Fermattest를 통과할 때까지 1을 유지하기 때문입니다. 또한 T는 다음 단계에서 1이 될 수 있고 1의 제곱근(다음 단계에서)이 +-1이기 때문에 T는 제곱근 테스트를 통과했습니다.
-
T가 다른 경우 n이 소수인지 합성인지 확실하지 않으므로 다음 단계로 계속 진행할 수 있습니다.
1단계 :우리는 T
-
결과가 +1이면 다음 테스트에 대해 T가 1로 유지되기 때문에 Fermat 테스트가 통과할 것임을 확실히 알 수 있습니다. 제곱근 테스트를 통과하지 못했습니다. T는 이 단계에서 1이고 이전 단계에서 +-1이 아닌 다른 값이기 때문에 n을 합성 및 중지로 선언할 수 있습니다.
-
결과가 -1이면 n이 결국 Fermat 테스트를 통과한다는 것을 이해할 수 있습니다. 또한 이 단계에서 T가 -1이고 다음 단계에서 1이 되기 때문에 제곱근 테스트를 통과한다는 것도 이해할 수 있습니다. n을 strongpseudoprime으로 선언하고 중지할 수 있습니다.
-
T가 다른 것이라면 소수를 가질 수 있는지 없는지 확실하지 않습니다. 다음 단계로 계속 진행합니다.
2단계에서 K단계 – 1단계:
이 단계와 이후의 모든 단계는 2단계와 K-1단계가 1단계와 동일할 때까지 계속됩니다.
K단계:
이 단계는 필요하지 않습니다. 이 단계에 도달할 수 있고 결정을 내리지 않은 경우 이 단계는 우리에게 제공하지 않습니다. 이 단계의 결과가 1이면 페르마 검정이 허용되지만 이전 단계의 결과가 +-1이 아니므로 제곱근 검정이 허용되지 않습니다. k -1 단계 이후에 아직 중지되지 않은 경우 n이 합성임을 선언할 수 있습니다. Miller-Rabin 테스트는 0단계부터 K-1단계까지 필요합니다.