C++-এ প্রাইম নম্বর n মডুলো n-এর প্রিমিটিভ রুট

এই সমস্যায় একটি প্রাইম নম্বর N দেওয়া আছে। N মডুলো N-এর প্রিমিটিভ রুট (primitive root) বের করতে হবে।

প্রিমিটিভ রুট হলো [1, n-1] রেঞ্জের একটি পূর্ণসংখ্যা x যাতে xᵏ (mod n) এর সব মান k ∈ [0, n-2] রেঞ্জে ইউনিক হয়।

উদাহরণ:

ইনপুট: 13 আউটপুট: 2

সমাধান: অয়লারের টোটিয়েন্ট ফাংশন (Euler's Totient Function) ব্যবহার করব। এটি ১ থেকে n পর্যন্ত যেসব সংখ্যা n-এর সাথে রিলেটিভলি প্রাইম (GCD=1), তাদের গণনা। যদি x মডুলো n-এর মাল্টিপ্লিকেটিভ অর্ডার টোটিয়েন্ট ফাংশনের সমান হয়, তবে x প্রিমিটিভ রুট। নোট: প্রাইম n-এর জন্য টোটিয়েন্ট ফাংশন = n-1।

উদাহরণ

#include<bits/stdc++.h>
using namespace std;

bool isPrimeNumber(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
            return false;
    return true;
}

int power(int x, unsigned int y, int p) {
    int res = 1;
    x = x % p;
    while (y > 0){
        if (y & 1)
            res = (res*x) % p;
        y = y >> 1;
        x = (x*x) % p;
    }
    return res;
}

void GeneratePrimes(unordered_set<int> &s, int n) {
    while (n%2 == 0){
        s.insert(2);
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i+2){
        while (n%i == 0){
            s.insert(i);
            n = n/i;
        }
    }
    if (n > 2)
        s.insert(n);
}

int findPrimitiveRoot(int n) {
    unordered_set<int> s;
    if (isPrimeNumber(n)==false)
        return -1;
    int ETF = n-1;
    GeneratePrimes(s, ETF);
    for (int r=2; r<=ETF; r++){
        bool flag = false;
        for (auto it = s.begin(); it != s.end(); it++){
            if (power(r, ETF/(*it), n) == 1){
                flag = true;
                break;
            }
        }
        if (flag == false)
            return r;
    }
    return -1;
}

int main() {
    int n= 13;
    cout << " Smallest primitive root of " << n << " is " << findPrimitiveRoot(n);
    return 0;
}

আউটপুট

Smallest primitive root of 13 is 2