Primitive Root ของจำนวนเฉพาะ n โมดูลโล n ใน C++

ภาพรวมปัญหา

ได้รับจำนวนเฉพาะ N ต้องหา Primitive Root ของ N โมดูลโล N

Primitive Root คือจำนวนเต็ม x ในช่วง [1, n-1] ที่ทำให้ค่า x^k (mod n) สำหรับ k ใน [0, n-2] เป็นค่าที่ไม่ซ้ำกันทั้งหมด

ตัวอย่าง

Input: 13
Output: 2

ทฤษฎีทางคณิตศาสตร์

ใช้ Euler's Totient Function (ETF) - จำนวนเต็มใน [1, n] ที่เป็นสัมพรธกับ n

สำหรับจำนวนเฉพาะ n: ETF = n-1

ถ้า multiplicative order ของ x โมดูลโล n เท่ากับ ETF → x เป็น primitive root

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

#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)) 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) 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