Tìm số gốc nguyên thủy modulo nguyên tố 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à tìm số nguyên tố gốc modulo nguyên tố .

Gốc ban đầu của một số - Là một số (r) nhỏ hơn N có tất cả các giá trị của r ^ x (mod N) khác nhau với mọi X trong phạm vi [0, n-2].

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

Input : N = 5
Output : 2

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là dựa trên phương pháp thử. Chúng tôi sẽ kiểm tra tất cả các số từ 2 đến (N-1) để tìm các điều kiện với x nằm trong khoảng từ [0, n-2] và ngắt nếu tìm thấy giá trị thỏa mãn điều kiện.

Giải pháp này khá đơn giản và dễ thực hiện nhưng độ phức tạp về thời gian của giải pháp là N ² . Điều này có thể dẫn đến thời gian chạy dài trong trường hợp giá trị N.

Vì vậy, một giải pháp hiệu quả hơn cho vấn đề là sử dụng hàm Euler Totient φ (N)

Vì vậy, để một số r là căn nguyên của N. Bậc nhân của nó với modulo N bằng φ (N). Dưới đây là các bước để làm theo -

Chúng ta cần tìm tất cả các thừa số nguyên tố của (N-1) cho số nguyên tố N. Sau đó tính tất cả các lũy thừa bằng cách sử dụng (N-1) / thừa số nguyên tố. Sau đó kiểm tra giá trị của các số nguyên tố power modulo n. Nếu nó không bao giờ là 1 thì i là gốc nguyên thủy. Giá trị đầu tiên mà chúng ta nhìn thấy sẽ là giá trị trả về vì có thể có nhiều hơn một căn nguyên cho một số nhưng chúng ta chỉ cần một căn nhỏ nhất.

Ví dụ

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

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

Đầu ra

The smallest primitive root is 3