इस समस्या में, हमें एक अभाज्य संख्या N दी गई है। हमारा कार्य अभाज्य मॉड्यूलो के तहत आदिम मूलों की संख्या ज्ञात करना है।
किसी संख्या का आदिम मूल - यह एक संख्या (r) है जो N से छोटी है जिसके लिए r^x (mod N) के सभी मान, [0, n-2] रेंज में सभी X के लिए भिन्न होते हैं।
उदाहरण से समझते हैं:
इनपुट: N = 5 आउटपुट: 2
समाधान दृष्टिकोण
समस्या का एक सरल समाधान परीक्षण विधि पर आधारित है। हम 2 से (N-1) तक सभी संख्याओं की जांच करेंगे, x को [0, n-2] रेंज में लेकर, और यदि कोई मान शर्त को संतुष्ट करता है तो ब्रेक कर देंगे।
यह समाधान सरल है और लागू करने में आसान है लेकिन समाधान की समय जटिलता N2 क्रम की है। N के बड़े मान के मामले में यह लंबा चल सकता है।
इसलिए, समस्या का एक अधिक कुशल समाधान ऑयलर टॉशिएंट फंक्शन φ(N) का उपयोग करके है।
तो, एक संख्या r के लिए N का आदिम मूल होने के लिए, मॉड्यूलो N के साथ इसका गुणन क्रम φ(N) के बराबर होना चाहिए। यहां अनुसरण करने के चरण हैं:
हमें अभाज्य संख्या N के लिए (N-1) के सभी अभाज्य गुणनखंड ढूंढने होंगे। फिर (N-1) / अभाज्य गुणनखंड का उपयोग करके सभी घातों की गणना करें। फिर अभाज्य संख्याओं के घात मॉड्यूलो n के मान की जांच करें। यदि यह कभी 1 नहीं है तो i आदिम मूल है। पहला मान जो हम देखेंगे वही लौटाया जाएगा क्योंकि एक संख्या के लिए एक से अधिक आदिम मूल हो सकते हैं लेकिन हमें सबसे छोटा चाहिए।
उदाहरण
समस्या को समझने के लिए एक उदाहरण लेते हैं:
#include<bits/stdc++.h> using namespace std; int calcPowerMod(int x, unsigned int y, int p){ int modVal = 1; x = x % p; while (y > 0){ if (y & 1) modVal = (modVal*x) % p; y = y >> 1; x = (x*x) % p; } return modVal; } void findAllPrimeFactors(unordered_set<int> &s, int n){ while (n%2 == 0){ s.insert(2); n = n/2; } for (int i = 3; i*i <= n; i = i+2){ while (n%i == 0){ s.insert(i); n = n/i; } } if (n > 2) s.insert(n); } int findSmallestPrimitiveRoot(int n){ unordered_set<int> primes; int phi = n-1; findAllPrimeFactors(primes, phi); for (int r=2; r<=phi; r++){ bool flag = false; for (auto it = primes.begin(); it != primes.end(); it++){ if (calcPowerMod(r, phi/(*it), n) == 1){ flag = true; break; } } if (flag == false) return r; } return -1; } int main(){ int n = 809; cout<<"The smallest primitive root is "<<findSmallestPrimitiveRoot(n); return 0; } आउटपुट
The smallest primitive root is 3
