বেইলি-পিএসডব্লিউ প্রাইম্যালিটি টেস্ট (Baillie-PSW Primality Test), এই টেস্ট রবার্ট বেইলি, কার্ল পোমেরেন্স, জন সেলফরিজ, এবং স্যামুয়েল ওয়াগস্টাফের নামের পর নামকরণ করা হয়েছে। এটি একটি টেস্ট যা পরীক্ষা করে কোনো সংখ্যা কম্পোজিট (composite) নাকি সম্ভাব্য প্রাইম।
আলগরিদম
MillerTest()
Begin
Declare a function MillerTest of Boolean type.
Declare MT_dt and MT_num of integer datatype and pass as parameter.
Declare MT_a and MT_x of integer datatype.
Initialize MT_a = 2 + rand() % (MT_num - 4).
Initialize MT_x = pow(MT_a, MT_dt, MT_num).
if (MT_x == 1 || MT_x == MT_num - 1) then return true.
while (MT_dt != MT_num - 1) do
MT_x = (MT_x * MT_x) % MT_num.
MT_dt *= 2.
if (MT_x == 1) then return false;
if (MT_x == MT_num - 1) then return true.
return false.
End.
উদাহরণ
#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, 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;
}
আউটপুট
Enter the first number: 23 23 is a prime number Enter another number: 45 45 is a composite number
