C++で素数を法とする原始根の数を求めます。

この問題では、素数Nが与えられます。私たちのタスクは素数を法とする原始根の数を見つけることです 。

数の原始根 −これはNよりも小さい数（r）であり、範囲[0、n-2]のすべてのXでr ^ x（mod N）のすべての値が異なります。

問題を理解するために例を見てみましょう

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