Baillie-PSW 소수성 테스트는 Robert Baillie, Carl Pomerance, John Selfridge, Samuel Wagstaff 네 사람의 이름을 딴 소수 판별 알고리즘입니다. 이 테스트는 주어진 수가 합성수(composite number)인지, 아니면 소수일 가능성이 있는 수인지를 판별합니다.
완전한 Baillie-PSW 테스트는 강한 유사소수 검사(밀러-라빈 테스트)와 뤼카(Lucas) 테스트를 결합한 형태이며, 흥미롭게도 아직까지 이 테스트를 통과하면서 실제로는 합성수인 반례는 단 하나도 발견되지 않았습니다. 아래 예제에서는 그 핵심인 밀러-라빈(Miller-Rabin) 방식의 소수성 검사를 C++로 구현하는 방법을 살펴보겠습니다.
알고리즘
MillerTest() 의사코드
시작
Boolean 타입의 함수 MillerTest를 선언한다.
정수형 매개변수 MT_dt와 MT_num을 받는다.
정수형 변수 MT_a와 MT_x를 선언한다.
MT_a = 2 + rand( ) % (MT_num - 4) 로 초기화
MT_x = pow(MT_a, MT_dt, MT_num) 으로 초기화
만약 (MT_x == 1 또는 MT_x == MT_num - 1)이라면
true를 반환한다.
MT_dt가 MT_num - 1이 될 때까지 다음을 반복한다.
MT_x = (MT_x * MT_x) % MT_num
MT_dt *= 2
만약 MT_x == 1이면 false를 반환한다.
만약 MT_x == MT_num - 1이면 true를 반환한다.
false를 반환한다.
끝.
C++ 구현 예제
#include <iostream>
#include<stdlib.h>
using namespace std;
int pow(int pow_a, unsigned int pow_b, int pow_c) {
int result = 1;
pow_a = pow_a % pow_c;
while (pow_b > 0) {
if (pow_b & 1)
result = (result * pow_a) % pow_c;
pow_b = pow_b >> 1;
pow_a = (pow_a * pow_a) % pow_c;
}
return result;
}
bool MiillerTest(int MT_dt, int MT_num) {
int MT_a = 2 + rand( ) % (MT_num - 4);
int MT_x = pow(MT_a, MT_dt, MT_num);
if (MT_x == 1 || MT_x == MT_num - 1)
return true;
while (MT_dt != MT_num - 1) {
MT_x = (MT_x * MT_x) % MT_num;
MT_dt *= 2;
if (MT_x == 1)
return false;
if (MT_x == MT_num - 1)
return true;
}
return false;
}
bool prime(int P_N, int P_K) {
if (P_N <= 1 || P_N == 4)
return false;
if (P_N <= 3)
return true;
int P_D = P_N - 1;
while (P_D % 2 == 0)
P_D /= 2;
for (int i = 0; i < P_K; i++)
if (MiillerTest(P_D, P_N) == false)
return false;
return true;
}
int main() {
int iter = 50;
long num1;
long num2;
cout<< "Enter the first number: ";
cin>>num1;
cout<<endl;
if (prime(num1, iter))
cout<<num1<<" is a prime number\n"<<endl;
else
cout<<num1<<" is a composite number\n"<<endl;
cout<<"Enter another number: ";
cin>>num2;
cout<<endl;
if (prime(num2, iter))
cout<<num2<<" is a prime number\n"<<endl;
else
cout<<num2<<" is a composite number\n"<<endl;
return 0;
}
코드 설명
- pow() 함수: 비트 시프트를 활용한 분할 정복 기법으로 모듈러 거듭제곱(ab mod c)을 빠르게 계산합니다. 큰 지수를 다룰 때 필수적인 최적화입니다.
- MiillerTest() 함수: 2부터 n-4 사이에서 무작위로 밑(base) a를 선택한 뒤, 밀러-라빈 검사를 한 라운드 수행합니다. 조건을 만족하지 못하면 해당 수는 합성수로 판정됩니다.
- prime() 함수: n이 4 이하인 특수한 경우를 먼저 처리하고, n-1에서 2의 인수를 모두 제거하여 홀수 d를 구합니다. 이후 K번(예제에서는 50회) 반복 검사를 통해 오판 확률을 크게 낮춥니다.
실행 결과
Enter the first number: 23 23 is a prime number Enter another number: 45 45 is a composite number
실행 결과를 보면 23은 소수로, 45는 합성수로 올바르게 판별되었습니다. 밀러-라빈 테스트는 확률적 알고리즘이지만, 반복 횟수 K를 늘릴수록 합성수를 소수로 잘못 판정할 확률이 지수적으로 감소하기 때문에 K=50 수준이면 실용적으로 매우 신뢰할 수 있는 판별이 가능합니다.