এই সমস্যায়, আমাদের একটি মৌলিক সংখ্যা N দেওয়া হয়েছে। আমাদের কাজ হল আদিম মূলের সংখ্যা খুঁজে বের করা মডুলো প্রাইম .
একটি সংখ্যার আদিম মূল − এটি একটি সংখ্যা (r) N এর থেকে ছোট যার r^x(mod N) এর সমস্ত মান রয়েছে [0, n-2] রেঞ্জের সমস্ত X এর জন্য আলাদা।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : N = 5 Output : 2
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান একটি ট্রায়াল পদ্ধতির উপর ভিত্তি করে। আমরা 2 থেকে (N-1) পর্যন্ত সমস্ত সংখ্যার জন্য পরীক্ষা করব যেখানে x থেকে [0, n-2] পরিসরের শর্ত রয়েছে এবং যদি এমন একটি মান পাওয়া যায় যা শর্ত পূরণ করে।
এই সমাধানটি নিষ্পাপ এবং কার্যকর করা সহজ কিন্তু সমাধানের সময় জটিলতা হল 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
