C++에서 기본 근의 수를 모듈로 소수로 구합니다.

이 문제에서 소수 N이 주어집니다. 우리의 임무는 modulo 소수의 기본 근의 수를 찾는 것입니다. .

숫자의 기본 근 - [0, n-2] 범위의 모든 X에 대해 다른 r^x(mod N)의 모든 값을 갖는 N보다 작은 숫자(r)입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

Input : N = 5
Output : 2

솔루션 접근 방식

문제에 대한 간단한 솔루션은 시험 방법을 기반으로 합니다. x 범위가 [0, n-2]인 조건에 대해 2부터 (N-1)까지의 모든 숫자를 확인하고 조건을 충족하는 값이 발견되면 중단합니다.

이 솔루션은 단순하고 구현하기 쉽지만 솔루션의 시간 복잡성은 N ² 정도입니다. . 이는 N 값이 큰 경우 장기 실행으로 이어질 수 있습니다.

따라서 문제에 대한 보다 효율적인 솔루션은 오일러 토티언트 함수 φ(N)

따라서 숫자 r은 N의 기본 근이 됩니다. 모듈로 N과의 곱셈 차수는 φ(N)과 같습니다. 다음은 따라야 할 단계입니다 -

소수 N에 대한 (N-1)의 모든 소인수를 찾아야 합니다. 그런 다음 (N-1) / 소인수를 사용하여 모든 거듭제곱을 계산합니다. 그런 다음 소수 거듭제곱 모듈로 n의 값을 확인합니다. 1이 아닌 경우 i는 기본 루트입니다. 숫자에 대해 둘 이상의 기본 루트가 있을 수 있지만 가장 작은 루트만 필요하므로 첫 번째 값은 반환된 값입니다.

예시

문제를 이해하기 위해 예를 들어보겠습니다.

#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