베일리–PSW 소수판별법

베일리-PSW 소수판별법은 어떤 수가 소수인지 합성수인지를 확인할 수 있는 확률론적 알고리즘이다.

개요

베일리-PSW 소수판별법은 a=2일 때의 밀러-라빈 소수판별법의 유사소수 (pseudopirme)와 뤼카 소수판별법의 유사소수가 거의 없다는 점을 이용한다. 밑이 2일 때 밀러-라빈 소수판별법의 첫 열 번째 유사소수들은 다음과 같다:

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 그리고 52633 (OEIS의 수열 A001262)

또한 강한 뤼카 소수판별법의 첫 열 번째 유사소수들 (여기서 P, Q는 셀프리지의 방법 A로 선택된 (P, Q) 쌍이다)은 다음과 같다:

5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, 그리고 58519 (OEIS의 수열 A217255)

위 두 수열에서 중복되는 수는 매우 적으며, 특히 위 두 수열에 모두 포함되면서 소수라면 만족해야 할 특정 조건들을 만족하는 합성수는 훨씬 적다는 것이 알려져 있다. 베일리-PSW 소수판별법은 바로 이 점을 이용하여 효과적으로 어떤 수가 소수인지 합성수인지를 판별한다. 베일리-PSW 소수판별법은 2⁶⁴ 미만의 수에 대해서는 검사를 진행했을 때 단 한 번도 틀리지 않았지만, 합성수이지만 확률적 소수라고 출력되는 수는 극히 적긴 하지만 무한히 많이 있을 것으로 추측된다.

알고리즘

입력: 정수 N>1

출력: 확률적 소수 또는 합성수

(1) 어떤 특정 한계값까지 자연수로 직접 나눠 본다. 만약 하나라도 나누어떨어진다면 합성수를 출력한다.

(2) 밑이 2일 때, 즉 a=2일 때 밀러-라빈 소수판별법을 실행한다. 만약 결과가 합성수로 나온다면 합성수를 출력한다.

(3) 이 과정에서는 두 가지 방법이 있다.

(A) 수열 5, -7, 9, -11, 13, -17, 19, ...에서 ${\displaystyle \left({\frac {D}{N}}\right)=-1}$인 첫 번째 D를 찾고, P=1, Q=(1-D)/4로 놓는다. 만약 Q=-1이라면 P=5, Q=5로 다시 설정한다.

(B) 수열 5, 9, 13, 17, 21, ...에서 ${\displaystyle \left({\frac {D}{N}}\right)=-1}$인 첫 번째 D를 찾고, P는 ${\displaystyle {\sqrt {N}}}$보다 큰 첫 번째 홀수, Q=(P²-D)/4로 놓는다. 만약 Q=1이라면

${\displaystyle Q\Leftarrow P+Q+1,P\Leftarrow P+2}$로 다시 설정한다.

(4) 과정 (3)에서 정한 D, P, Q에 대해 강한 뤼카 소수판별법을 적용한다. 만약 이 과정에서 결과가 합성수로 나오면 합성수를 출력하고, 아니면 확률적 소수를 출력한다.