बेली-पीएसडब्ल्यू प्राइमैलिटी टेस्ट, यह टेस्ट रॉबर्ट बेली, कार्ल पोमेरेंस, जॉन सेल्फ्रिज, और सैमुअल वैगस्टाफ के नाम पर रखा गया है। यह एक टेस्ट है जो जांचता है कि कोई संख्या कम्पोजिट नंबर है या संभावित रूप से प्राइम।
एल्गोरिदम
मिलरटेस्ट()
Begin
बूलियन टाइप का फंक्शन 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) इनिशियलाइज़ करें।
if (MT_x == 1 || MT_x == MT_num - 1) तो
return true.
while (MT_dt != MT_num - 1) do
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.
End.
C++ कार्यान्वयन
#include <iostream>
#include <stdlib.h>
using namespace std;
int pow(int base, unsigned int exp, int mod) {
int result = 1;
base = base % mod;
while (exp > 0) {
if (exp & 1)
result = (result * base) % mod;
exp = exp >> 1;
base = (base * base) % mod;
}
return result;
}
bool MillerTest(int d, int n) {
int a = 2 + rand() % (n - 4);
int x = pow(a, d, n);
if (x == 1 || x == n - 1)
return true;
while (d != n - 1) {
x = (x * x) % n;
d *= 2;
if (x == 1) return false;
if (x == n - 1) return true;
}
return false;
}
bool isPrime(int n, int k) {
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
int d = n - 1;
while (d % 2 == 0) d /= 2;
for (int i = 0; i < k; i++)
if (MillerTest(d, n) == false)
return false;
return true;
}
int main() {
int iter = 50;
long num1, num2;
cout << "Enter the first number: ";
cin >> num1;
if (isPrime(num1, iter))
cout << num1 << " is a prime number\n";
else
cout << num1 << " is a composite number\n";
cout << "Enter another number: ";
cin >> num2;
if (isPrime(num2, iter))
cout << num2 << " is a prime number\n";
else
cout << num2 << " is a composite number\n";
return 0;
}
आउटपुट
Enter the first number: 23 23 is a prime number Enter another number: 45 45 is a composite number
नोट
यह कार्यान्वयन मिलर-रैबिन टेस्ट दिखाता है जो बेली-पीएसडब्ल्यू का एक भाग है। पूर्ण बेली-पीएसडब्ल्यू टेस्ट में लुकास टेस्ट भी शामिल होता है। यह कोड शैक्षिक उद्देश्यों के लिए सरलीकृत संस्करण है।