C++で素数を法とする原始根を求める方法

問題概要

この問題では、素数 N が与えられ、素数を法とする原始根(Primitive Root)を求めることが課題となります。

原始根とは — N より小さい数 r のうち、[0, n-2] の範囲のすべての x に対して r^x (mod N) の値が互いに異なるような数のことを指します。

例を見て理解しましょう:

入力 : N = 5
出力 : 2

なお、数学的には素数 N を法とする原始根の総個数は φ(N−1)(オイラー関数の値)であることが知られています。本記事では、その中でも最小の原始根を効率よく求める手法を紹介します。

解法アプローチ

1. 素朴な解法(全探索)

最も単純な解法は試行錯誤(全探索)によるものです。2 から (N−1) までのすべての数について、x を [0, n-2] の範囲で動かしながら条件を満たすかを順に確認し、条件を満たす値が見つかった時点で探索を終了します。

この方法は実装が簡単ですが、時間計算量が O(N²) となるため、N が大きい場合は実行に非常に長い時間がかかる可能性があります。

2. オイラーのトーティエント関数を用いた効率的な解法

より効率的なアプローチとして、オイラーのトーティエント関数 φ(N) を活用します。

数 r が N の原始根であるためには、法 N における r の乗法位数が φ(N) と一致する必要があります。具体的な手順は以下の通りです。

• まず、素数 N に対して (N−1) のすべての素因数を求めます。
• 次に、(N−1) を各素因数で割った値を指数として冪乗を計算します。
• その冪乗を mod n で評価し、結果が一度も 1 にならないならば、r は原始根です。

原始根は複数存在しうるため、最初に見つかった値(すなわち最小の原始根)を返却すればよいことになります。

サンプルコード(C++)

#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

このように、素因数分解と繰り返し二乗法(べき乗の剰余計算)を組み合わせることで、大きな素数に対しても高速に最小の原始根を求めることができます。