ในปัญหานี้ เราได้รับจำนวนเฉพาะ N หน้าที่ของเราคือ หาจำนวนโมดูโลไพรม์ของรากดั้งเดิม .
รากดั้งเดิมของตัวเลข − เป็นตัวเลข (r) ที่น้อยกว่า N ซึ่งมีค่าทั้งหมดของ r^x(mod N) ที่แตกต่างกันสำหรับ X ทั้งหมดในช่วง [0, n-2]
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
Input : N = 5 Output : 2
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายขึ้นอยู่กับวิธีการทดลองใช้ เราจะตรวจสอบตัวเลขทั้งหมดตั้งแต่ 2 ถึง (N-1) สำหรับเงื่อนไขที่มี x ตั้งแต่ [0, n-2] และแตกหากพบค่าที่ตรงตามเงื่อนไข
โซลูชันนี้ไร้เดียงสาและใช้งานง่าย แต่ความซับซ้อนของเวลาของโซลูชันอยู่ในลำดับของ N 2 . ซึ่งอาจนำไปสู่การดำเนินการระยะยาวในกรณีที่มีค่า N.
. มากดังนั้น วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นคือการใช้ฟังก์ชันออยเลอร์ โทเทียน φ(N)
ดังนั้น สำหรับจำนวน r จะเป็นรากดั้งเดิมของ N ลำดับการคูณด้วยโมดูโล N เท่ากับ φ(N) ต่อไปนี้เป็นขั้นตอนที่ต้องปฏิบัติตาม -
เราต้องหาตัวประกอบเฉพาะของ (N-1) สำหรับจำนวนเฉพาะ N แล้วคำนวณกำลังทั้งหมดโดยใช้ (N-1) / ตัวประกอบเฉพาะ จากนั้นตรวจสอบค่าของจำนวนเฉพาะกำลัง โมดูโล n ถ้ามันไม่ใช่ 1 แสดงว่าฉันเป็นรากดั้งเดิม ค่าแรกที่เราเห็นจะเป็นค่าที่ส่งคืน เนื่องจากมีรากดั้งเดิมมากกว่าหนึ่งค่าสำหรับตัวเลข แต่เราต้องการเพียงค่าที่น้อยที่สุดเท่านั้น
ตัวอย่าง
มาดูตัวอย่างทำความเข้าใจปัญหากัน
#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
