밀러-라빈 소수판별법 계산기

n-1을 2^r×d(d는 홀수)로 분해한 뒤 a^d부터 시작해 제곱해 나가면서, 그 과정에서 "1의 자명하지 않은 제곱근"(1도 n-1도 아닌데 제곱하면 1이 되는 값)이 나오는지도 함께 검사합니다. 소수를 법으로 하면 1의 제곱근은 반드시 ±1뿐이어야 하므로, 그렇지 않은 값이 나오면 그 자체로 합성수라는 증거가 됩니다.

561-1=560=2⁴×35이라 밑 2로 시작하면 2³⁵, 그 제곱, 또 제곱, … 순서로 263 → 166 → 67 → 1이 나옵니다. 마지막에 1이 되긴 하지만, 그 직전 값 67이 560(=n-1)이 아닙니다. 67²을 561로 나눈 나머지가 166이지 560이 아니므로, 67은 1의 자명하지 않은 제곱근이고 이것이 561이 합성수라는 증거입니다.

이론적으로는 561처럼 특정 밑에서 이 검사도 통과하는 합성수(강한 유사소수)가 존재할 수 있습니다. 다만 그런 밑은 전체 밑의 최대 4분의 1뿐이라는 것이 증명되어 있어, 무작위로 고른 밑 k개를 모두 통과했다면 합성수일 확률이 4^(-k)로 매우 빠르게 줄어듭니다. 라운드를 몇 번만 반복해도 실용적으로 충분히 신뢰할 수 있습니다.

작은 밑들을 고정해 쓰면 특정 범위 안에서는 결정적으로(오판정 없이) 소수를 판별할 수 있다는 결과들이 알려져 있습니다. 다만 이 계산기는 정확한 상한값을 출처 확인 없이 단정하지 않습니다 — 확률적 방법이라는 원리에 집중해 주세요.