সোলোভে-স্ট্রাসেন প্রাইম্যালিটি টেস্ট (Solovay-Strassen Primality Test) একটি সংখ্যা কম্পোজিট নাকি সম্ভাব্য প্রাইম কিনা তা টেস্ট করতে ব্যবহৃত হয়।
আলগরিদম
Begin
Declare a function modulo of long datatype to perform binary calculation.
Declare m_base, m_exp, m_mod of long datatype and pass as 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 Jacobian of int datatype to calculate Jacobian symbol.
Declare CJ_a, CJ_n of long datatype and pass as parameter.
if (!CJ_a) then return 0.
Declare answer of 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 of Boolean datatype.
Declare SS_p of long datatype and itr of integer datatype as parameter.
if (SS_p < 2) return false.
if (SS_p != 2 && SS_p % 2 == 0) 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) return false.
return true.
End
উদাহরণ
#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;
}
int Jacobian(long CJ_a, long CJ_n) {
if (!CJ_a) return 0;
int answer = 1;
if (CJ_a < 0) {
CJ_a = -CJ_a;
if (CJ_n % 4 == 3) answer = -answer;
}
if (CJ_a == 1) return 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) return answer;
return 0;
}
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++) {
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, 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
