C++ में अभाज्य संख्या n का आदिम मूल (Primitive Root) मॉड्यूलो n

इस समस्या में, हमें एक अभाज्य संख्या N दी गई है। हमारा कार्य अभाज्य संख्या N का आदिम मूल (primitive root) मॉड्यूलो N प्रिंट करना है।

आदिम मूल (Primitive root) अभाज्य संख्या N का एक पूर्णांक x है जो [1, n-1] के बीच होता है जैसे कि xᵏ (mod n) के सभी मान जहां k [0, n-2] में होता है, अद्वितीय (unique) होते हैं।

आइए एक उदाहरण से समझते हैं:

इनपुट: 13
आउटपुट: 2

इस समस्या को हल करने के लिए, हमें ऑयलर टॉशिएंट फंक्शन (Euler's Totient Function) नामक गणितीय फंक्शन का उपयोग करना होगा।

ऑयलर टॉशिएंट फंक्शन 1 से n तक उन संख्याओं की गिनती है जो संख्या n के सापेक्ष अभाज्य (relatively prime) हैं।

एक संख्या i सापेक्ष अभाज्य है यदि GCD(i, n) = 1।

समाधान में, यदि x का मॉड्यूलो n गुणात्मक क्रम (multiplicative order) ऑयलर टॉशिएंट फंक्शन के बराबर है, तो वह संख्या आदिम मूल है अन्यथा नहीं। हम सभी सापेक्ष अभाज्य संख्याओं के लिए जांच करेंगे।

नोट: एक अभाज्य संख्या 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 << "सबसे छोटा आदिम मूल " << n << " का है " << findPrimitiveRoot(n);
    return 0;
}

आउटपुट

सबसे छोटा आदिम मूल 13 का है 2