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