Solovay-Strassen 소수성 테스트는 숫자가 합성수인지 또는 소수일 가능성이 있는지 여부를 테스트하는 데 사용됩니다.
알고리즘
Begin Declare a function modulo to the long datatype to perform binary calculation. Declare m_base, m_exp, m_mod of long datatype and pass them as a parameter. Declare two variables a, b of long datatype. Initialize a = 1, b = m_base. while (m_exp > 0) do if (m_exp % 2 == 1) then a = (a * b) % m_mod. b = (b * b) % m_mod. m_exp = m_exp / 2. Return a % m_mod. End Begin Declare a function Jecobian of the int datatype to calculate Jacobian symbol of a given number. Declare CJ_a, CJ_n of the long datatype and pass them as a parameter. if (!CJ_a) then return 0. Declare answer of the integer datatype. Initialize answer = 1. if (CJ_a < 0) then CJ_a = -CJ_a. if (CJ_n % 4 == 3) then answer = -answer. if (CJ_a == 1) then return answer. while (CJ_a) do if (CJ_a < 0) then CJ_a = -CJ_a. if (CJ_n % 4 == 3) then answer = -answer. while (CJ_a % 2 == 0) do CJ_a = CJ_a / 2; if (CJ_n % 8 == 3 || CJ_n % 8 == 5) then answer = -answer. swap(CJ_a, CJ_n) if (CJ_a % 4 == 3 && CJ_n % 4 == 3) then answer = -answer. CJ_a = CJ_a % CJ_n; if (CJ_a > CJ_n / 2) then CJ_a = CJ_a - CJ_n. if (CJ_n == 1) then return answer. End Begin Declare a function Solovoystrassen to the Boolean datatype to perform the Solovay-Strassen Primality Test. Declare SS_p to the long datatype and pass as a parameter. Declare itr to the integer datatype and pass them as a parameter. if (SS_p < 2) then return false. if (SS_p != 2 && SS_p % 2 == 0) then return 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) then return false return true. End Begin Declare iter of the integer datatype. Initialize iter = 50. Declare num1, num2 of the long datatype. Print “Enter the first number:” Input the value of num1. if (Solovoystrassen(num1, iter)) then print the value of num1 and ”is a prime number”. Else print the value of num1 and ”is a composite number”. Print “Enter another number:” Input the value of num2. if (Solovoystrassen(num2, iter)) then print the value of num2 and ”is a prime number”. Else print the value of num2 and ”is a composite number”. End.
예시
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
long modulo(long m_base, long m_exp, long m_mod) // modulo
function to perform binary calculation {
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;
}
int Jacobian(long CJ_a, long CJ_n) { // calculate Jacobian symbol of a given number
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; // (-1/n) = -1 if n = 3 (mod 4)
}
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; // (-1/n) = -1 if n = 3 (mod 4)
}
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;
}
bool Solovoystrassen(long SS_p, int itr) { //perform the Solovay- Strassen Primality Test
if (SS_p < 2)
return false;
if (SS_p != 2 && SS_p % 2 == 0)
return false;
for (int i = 0; i < itr; i++) {
// Generate a random number 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;
}
// Driver Code
int main() {
int iter = 50;
long num1;
long num2;
cout<< "Enter the first number: ";
cin>>num1;
cout<<endl;
if (Solovoystrassen(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 (Solovoystrassen(num2, iter))
cout<<num2<<" is a prime number\n"<<endl;
else
cout<<num2<<" is a composite number\n"<<endl;
return 0;
} 출력
Enter the first number: 24 24 is a composite number Enter another number: 23 23 is a prime number