Căn nguyên của một số nguyên tố n modulo n trong C ++

Trong bài toán này, chúng ta được cho một số nguyên tố N. nhiệm vụ của chúng ta là in ra căn nguyên của số nguyên tố N modulo N.

Gốc ban đầu của số nguyên tố N là một số nguyên x nằm giữa [1, n-1] sao cho tất cả các giá trị của xk (mod n) trong đó k nằm trong [0, n-2] là duy nhất.

Hãy lấy một ví dụ để hiểu vấn đề,

Input: 13
Output: 2

Để giải quyết vấn đề này, chúng ta phải sử dụng hàm toán học có tên là Euler’s Totient Function .

Euler’s Totient Function là đếm các số từ 1 đến n tương đối nguyên tố với số n.

Một số i tương đối nguyên tố nếu GCD (i, n) =1.

Trong lời giải, nếu bậc nhân của x modulo n bằng Euler’s Totient Function, thì số đó là căn nguyên, ngược lại thì không. Chúng tôi sẽ kiểm tra tất cả các số nguyên tố tương đối.

Lưu ý:Hàm Euler’s Totient của một số nguyên tố n =n-1

Đoạn mã dưới đây sẽ hiển thị việc triển khai giải pháp của chúng tôi,

Ví dụ

#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;
}

Đầu ra

Smallest primitive root of 13 is 2