राबिन-मिलर अभाज्यता परीक्षण यह जांचने के लिए उपयोग किया जाता है कि दी गई संख्या अभाज्य है या नहीं। यह फर्मेट अभाज्यता परीक्षण और सोलोवे-स्ट्रैसेन परीक्षण के समान है। यह परीक्षण सबसे पहले रूसी गणितज्ञ एम. एम. आर्त्जुहोव द्वारा खोजा गया था।
एल्गोरिदम
शुरुआत ll mulmod(ll a, ll b, ll m) ll x = 0,y = a मॉड m जब तक (b > 0) यदि (b मॉड 2 == 1) x = (x + y) मॉड m की गणना करें y = (y * 2) मॉड m b = b/ 2 x मॉड m वापस करें। अंत शुरुआत ll मोड्यूलो(ll आधार, ll घात, ll m) आरंभ करें: ll x = 1 ll y = आधार जब तक (घात > 0) यदि (घात मॉड 2 == 1) x = (x * y) मॉड m y = (y * y) मॉड m घात = घात / 2; x मॉड m वापस करें अंत शुरुआत बूल मिलर(ll p, इंटरेशन) यदि (p < 2) वापस गलत यदि (p != 2 और p मॉड 2==0) वापस गलत; गणना करें: ll s = p - 1 जब तक (s मॉड 2 == 0) s = s/ 2; i = 0 से इंटरेशन - 1 तक करें ll a = रैंड() मॉड (p - 1) + 1, temp = s ll मॉड = मोड्यूलो(a, temp, p) जब तक (temp != p - 1 और मॉड != 1 और मॉड != p - 1) मॉड = mulmod(मॉड, मॉड, p); temp *= 2; यदि (मॉड != p - 1 && temp % 2 == 0) वापस गलत अन्यथा वापस सच अंत
उदाहरण कोड
#include <iostream> #include<stdlib.h> #define ll long long using namespace std; ll mulmod(ll a, ll b, ll m)//यह सच लौटाता है यदि संख्या अभाज्य है अन्यथा गलत { ll x = 0,y = a % m; while (b > 0) { if (b % 2 == 1) { x = (x + y) % m; } y = (y * 2) % m; b /= 2; } return x % m; } ll modulo(ll base, ll e, ll m) { ll x = 1; ll y = base; while (e > 0) { if (e % 2 == 1) x = (x * y) % m; y = (y * y) % m; e = e / 2; } return x % m; } bool Miller(ll p, int iteration) { if (p < 2) { return false; } if (p != 2 && p % 2==0) { return false; } ll s = p - 1; while (s % 2 == 0) { s /= 2; } for (int i = 0; i < iteration; i++) { ll a = rand() % (p - 1) + 1, temp = s; ll mod = modulo(a, temp, p); while (temp != p - 1 && mod != 1 && mod != p - 1) { mod = mulmod(mod, mod, p); temp *= 2; } if (mod != p - 1 && temp % 2 == 0) { return false; } } return true; } int main() { int iteration = 10; ll num; cout<<"अभाज्यता जांचने के लिए पूर्णांक दर्ज करें: "; cin>>num; if (Miller(num, iteration)) cout<<num<<" अभाज्य है"<<endl; else cout<<num<<" अभाज्य नहीं है"<<endl; return 0; }
आउटपुट
अभाज्यता जांचने के लिए पूर्णांक दर्ज करें: 26 26 अभाज्य नहीं है
