หาจำนวนรากโมดูลอ primitive roots modulo prime ใน C++

สำหรับจำนวน r ที่จะเป็น primitive root ของ N จะต้องมี multiplicative order modulo N เท่ากับ φ(N) ขั้นตอน:

1. หาตัวประกอบเฉพาะทั้งหมดของ (N-1)
2. คำนวณกำลังต่างๆ โดยใช้ (N-1) / prime_factors
3. ตรวจสอบค่า r^power (mod n) หากไม่เคยเป็น 1 แสดงว่า r เป็น primitive root

ตัวอย่างโค้ด

#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