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ố lượng gốc nguyên thủy modulo số nguyên tố.
Gốc nguyên thủy của một số − Là một số (r) nhỏ hơn N có tất cả giá trị r^x(mod N) khác nhau cho mọi X trong khoảng [0, n-2].
Hãy xem ví dụ sau để hiểu bài toán:
Input : N = 5 Output : 2
Phương pháp giải
Một giải pháp đơn giản dựa trên phương pháp thử. Ta kiểm tra tất cả số từ 2 đến (N-1) cho các điều kiện với x trong [0, n-2] và dừng nếu tìm thấy giá trị thỏa mãn.
Giải pháp này naiv và dễ cài đặt nhưng độ phức tạp thời gian bậc N2. Có thể dẫn đến thời gian chạy lâu với N lớn.
Vì vậy, giải pháp hiệu quả hơn là sử dụng hàm Euler Totient φ(N).
Vì vậy, để một số r là gốc nguyên thủy của N. Thứ bậc nhân của nó modulo N bằng φ(N). Các bước:
Ta cần tìm tất cả thừa số nguyên tố của (N-1) cho số nguyên tố N. Sau đó tính tất cả lũy thừa bằng (N-1) / thừa số nguyên tố. Kiểm tra giá trị lũy thừa số nguyên tố modulo n. Nếu không bao giờ bằng 1 thì i là gốc nguyên thủy. Giá trị đầu tiên tìm thấy sẽ được trả về vì có thể có nhiều gốc nguyên thủy nhưng ta chỉ cần nhỏ nhất.
Ví dụ
Hãy xem ví dụ để hiểu bài toá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; }Kết quả
The smallest primitive root is 3