इस समस्या में, हमें एक अभाज्य संख्या N दी जाती है। हमारा कार्य आदिम जड़ों की संख्या ज्ञात करना modulo prime है। ।
किसी संख्या का आदिम मूल - यह एक संख्या (r) है जो N से छोटी है जिसमें r^x(mod N) के सभी मान [0, n-2] श्रेणी में सभी X के लिए भिन्न हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
Input : N = 5 Output : 2
समाधान दृष्टिकोण
समस्या का एक सरल समाधान परीक्षण पद्धति पर आधारित है। हम x से लेकर [0, n-2] तक की स्थितियों के लिए 2 से (N-1) तक के सभी नंबरों की जांच करेंगे और अगर कोई मान मिलता है जो शर्त को पूरा करता है तो हम उसे तोड़ देंगे।
यह समाधान अनुभवहीन है और इसे लागू करना आसान है लेकिन समाधान की समय जटिलता N 2 के क्रम की है . यह 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