솔로베이-스트라센(Solovay-Strassen) 소수성 테스트는 오일러 준거(Euler Criterion)에 기반한 확률적 알고리즘으로, 주어진 수가 합성수인지 아니면 소수일 가능성이 높은지를 판별하는 데 사용됩니다. 이 테스트는 여러 번의 반복을 거치며 합성수를 소수로 오판할 확률을 지수적으로 낮추기 때문에, 큰 수의 소수 여부를 빠르게 검사해야 하는 상황에서 유용하게 활용됩니다.
알고리즘
전체 알고리즘은 세 가지 핵심 함수로 구성됩니다.
1. 모듈러 거듭제곱 함수 (modulo)
시작
이진 계산을 수행하기 위한 modulo 함수를 long 자료형으로 선언합니다.
long 자료형의 m_base, m_exp, m_mod를 매개변수로 전달합니다.
long 자료형의 변수 a, b를 선언합니다.
a = 1, b = m_base로 초기화합니다.
while (m_exp > 0) 동안 반복:
if (m_exp % 2 == 1)이면:
a = (a * b) % m_mod
b = (b * b) % m_mod
m_exp = m_exp / 2
a % m_mod를 반환합니다.
종료
2. 야코비 심볼 계산 함수 (Jacobian)
시작
주어진 수의 야코비 심볼(Jacobian Symbol)을 계산하기 위해 int 자료형의 Jacobian 함수를 선언합니다.
long 자료형의 CJ_a, CJ_n을 매개변수로 전달합니다.
if (!CJ_a)이면:
0을 반환합니다.
int 자료형의 answer를 선언하고 1로 초기화합니다.
if (CJ_a < 0)이면:
CJ_a = -CJ_a
if (CJ_n % 4 == 3)이면:
answer = -answer
if (CJ_a == 1)이면:
answer를 반환합니다.
while (CJ_a) 동안 반복:
if (CJ_a < 0)이면:
CJ_a = -CJ_a
if (CJ_n % 4 == 3)이면:
answer = -answer
while (CJ_a % 2 == 0) 동안 반복:
CJ_a = CJ_a / 2
if (CJ_n % 8 == 3 또는 CJ_n % 8 == 5)이면:
answer = -answer
swap(CJ_a, CJ_n)
if (CJ_a % 4 == 3 그리고 CJ_n % 4 == 3)이면:
answer = -answer
CJ_a = CJ_a % CJ_n
if (CJ_a > CJ_n / 2)이면:
CJ_a = CJ_a - CJ_n
if (CJ_n == 1)이면:
answer를 반환합니다.
종료
3. Solovay-Strassen 소수성 테스트 함수
시작
bool 자료형의 Solovoystrassen 함수를 선언하여 Solovay-Strassen 소수성 테스트를 수행합니다.
long 자료형의 SS_p와 int 자료형의 itr을 매개변수로 전달합니다.
if (SS_p < 2)이면:
false를 반환합니다.
if (SS_p != 2 그리고 SS_p % 2 == 0)이면:
false를 반환합니다.
for (int i = 0; i < itr; i++) 반복:
long a = rand() % (SS_p - 1) + 1
long jacob = (SS_p + Jacobian(a, SS_p)) % SS_p
long mod = modulo(a, (SS_p - 1) / 2, SS_p)
if (!jacob 또는 mod != jacob)이면:
false를 반환합니다.
true를 반환합니다.
종료
4. 메인 함수 (드라이버 코드)
시작
int 자료형의 iter를 선언하고 50으로 초기화합니다.
long 자료형의 num1, num2를 선언합니다.
"첫 번째 숫자를 입력하세요:"를 출력합니다.
num1 값을 입력받습니다.
if (Solovoystrassen(num1, iter))이면:
num1과 "은(는) 소수입니다"를 출력합니다.
else:
num1과 "은(는) 합성수입니다"를 출력합니다.
"다른 숫자를 입력하세요:"를 출력합니다.
num2 값을 입력받습니다.
if (Solovoystrassen(num2, iter))이면:
num2와 "은(는) 소수입니다"를 출력합니다.
else:
num2와 "은(는) 합성수입니다"를 출력합니다.
종료.
C++ 예제 코드
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
// 모듈러 거듭제곱을 수행하는 함수 (이진 계산 방식)
long modulo(long m_base, long m_exp, long m_mod) {
long a = 1;
long b = m_base;
while (m_exp > 0) {
if (m_exp % 2 == 1)
a = (a * b) % m_mod;
b = (b * b) % m_mod;
m_exp = m_exp / 2;
}
return a % m_mod;
}
// 주어진 수의 야코비 심볼(Jacobian Symbol)을 계산하는 함수
int Jacobian(long CJ_a, long CJ_n) {
if (!CJ_a)
return 0; // (0/n) = 0
int answer = 1;
if (CJ_a < 0) {
CJ_a = -CJ_a; // (a/n) = (-a/n)*(-1/n)
if (CJ_n % 4 == 3)
answer = -answer; // n ≡ 3 (mod 4)일 때 (-1/n) = -1
}
if (CJ_a == 1)
return answer; // (1/n) = 1
while (CJ_a) {
if (CJ_a < 0) {
CJ_a = -CJ_a; // (a/n) = (-a/n)*(-1/n)
if (CJ_n % 4 == 3)
answer = -answer; // n ≡ 3 (mod 4)일 때 (-1/n) = -1
}
while (CJ_a % 2 == 0) {
CJ_a = CJ_a / 2;
if (CJ_n % 8 == 3 || CJ_n % 8 == 5)
answer = -answer;
}
swap(CJ_a, CJ_n);
if (CJ_a % 4 == 3 && CJ_n % 4 == 3)
answer = -answer;
CJ_a = CJ_a % CJ_n;
if (CJ_a > CJ_n / 2)
CJ_a = CJ_a - CJ_n;
}
if (CJ_n == 1)
return answer;
return 0;
}
// Solovay-Strassen 소수성 테스트 수행
bool Solovoystrassen(long SS_p, int itr) {
if (SS_p < 2)
return false;
if (SS_p != 2 && SS_p % 2 == 0)
return false;
for (int i = 0; i < itr; i++) {
// 무작위 수 a 생성
long a = rand() % (SS_p - 1) + 1;
long jacob = (SS_p + Jacobian(a, SS_p)) % SS_p;
long mod = modulo(a, (SS_p - 1) / 2, SS_p);
if (!jacob || mod != jacob)
return false;
}
return true;
}
// 드라이버 코드
int main() {
int iter = 50;
long num1;
long num2;
cout<< "첫 번째 숫자를 입력하세요: ";
cin>>num1;
cout<<endl;
if (Solovoystrassen(num1, iter))
cout<<num1<<" 은(는) 소수입니다\n"<<endl;
else
cout<<num1<<" 은(는) 합성수입니다\n"<<endl;
cout<<"다른 숫자를 입력하세요: ";
cin>>num2;
cout<<endl;
if (Solovoystrassen(num2, iter))
cout<<num2<<" 은(는) 소수입니다\n"<<endl;
else
cout<<num2<<" 은(는) 합성수입니다\n"<<endl;
return 0;
}
실행 결과
첫 번째 숫자를 입력하세요: 24 24 은(는) 합성수입니다 다른 숫자를 입력하세요: 23 23 은(는) 소수입니다
동작 원리 및 특징
Solovay-Strassen 테스트는 오일러 준거를 활용합니다. p가 홀수인 소수라면 임의의 정수 a에 대해 다음 식이 성립합니다.
a(p−1)/2 ≡ (a/p) (mod p)
여기서 (a/p)는 야코비 심볼입니다. 만약 p가 합성수라면 이 등식을 만족하지 않는 a가 존재하므로, 무작위로 선택한 a에 대해 등식이 깨지면 해당 수는 확실하게 합성수로 판정할 수 있습니다.
이 테스트의 오류 확률도 중요한 특징입니다. 한 번의 반복에서 합성수를 소수로 잘못 판정할 확률은 최대 1/2이며, k번 반복하면 (1/2)k로 급격히 감소합니다. 위 예제에서는 iter = 50으로 설정했으므로 오판 확률이 약 10-15 수준으로 사실상 무시할 수 있을 만큼 작아집니다.