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

この問題では、素数Nが与えられ、その素数Nを法とする原始根（primitive root）を求めて出力することが課題となります。

原始根とは？

素数Nの原始根とは、1以上N-1以下の範囲に存在する整数xのことで、kが0からN-2までの範囲にあるとき、x^k (mod N) の値がすべて異なる（一意である）ような整数を指します。

具体例で確認してみましょう。

入力：13
出力：2

この場合、2は13の原始根です。実際に計算すると、2⁰, 2¹, 2², ..., 2¹¹ を法13で計算した結果はすべて異なる値となり、1〜12のすべての値をちょうど一度ずつ取ることが確認できます。

解法のアプローチ：オイラーのトーティエント関数

この問題を解くには、オイラーのトーティエント関数（Euler's Totient Function）という数学的関数を利用します。

オイラーのトーティエント関数とは、1からnまでの整数のうち、nと互いに素（GCD(i, n) = 1）である数の個数を表す関数です。

重要な性質として、素数nに対するオイラーのトーティエント関数の値は n-1 となります。これは、素数nより小さい正の整数はすべてnと互いに素だからです。

判定方法

解法の核心は次の通りです。ある整数xの「乗法位数」（xを何乗すると初めて mod n で1になるか）が、オイラーのトーティエント関数の値 φ(n) = n-1 と等しければ、そのxは原始根であると判定できます。逆に、それより小さい位数しか持たなければ原始根ではありません。

効率的に判定するためには、φ(n) の約数ではなく、φ(n) の素因数を使って検証します。具体的には、φ(n) を素因数分解し、各素因数qについて x^(φ(n)/q) mod n ≠ 1 がすべての素因数qで成り立てば、xは原始根であると結論できます。

C++での実装例

以下のコードは、上記の解法を実装したものです。

#include<bits/stdc++.h>
using namespace std;

// 素数判定関数
bool isPrimeNumber(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
            return false;
    return true;
}

// 繰り返し二乗法によるべき乗計算 (x^y mod p)
int power(int x, unsigned int y, int p) {
    int res = 1;
    x = x % p;
    while (y > 0){
        if (y & 1)
            res = (res*x) % p;
        y = y >> 1;
        x = (x*x) % p;
    }
    return res;
}

// nの素因数を集合sに格納
void GeneratePrimes(unordered_set<int> &s, int n) {
    while (n%2 == 0){
        s.insert(2);
        n = n/2;
    }
    for (int i = 3; i <= sqrt(n); i = i+2){
        while (n%i == 0){
            s.insert(i);
            n = n/i;
        }
    }
    if (n > 2)
        s.insert(n);
}

// 最小の原始根を探索
int findPrimitiveRoot(int n) {
    unordered_set<int> s;
    if (isPrimeNumber(n)==false)
        return -1;
    int ETF = n-1; // オイラーのトーティエント関数の値
    GeneratePrimes(s, ETF);
    for (int r=2; r<=ETF; r++){
        bool flag = false;
        for (auto it = s.begin(); it != s.end(); it++){
            // r^(ETF/q) mod n == 1 なら原始根ではない
            if (power(r, ETF/(*it), n) == 1){
                flag = true;
                break;
            }
        }
        if (flag == false)
            return r;
    }
    return -1;
}

int main() {
    int n = 13;
    cout << " Smallest primitive root of " << n << " is " << findPrimitiveRoot(n);
    return 0;
}

実行結果

Smallest primitive root of 13 is 2

コードのポイント

• isPrimeNumber関数：6k±1の性質を利用した高速な素数判定を行います。
• power関数：繰り返し二乗法（バイナリ法）により、大きな指数の冪乗も O(log y) の時間計算量で効率的に mod p で計算できます。
• GeneratePrimes関数：n-1を素因数分解し、素因数をunordered_setに格納します。
• findPrimitiveRoot関数：候補rを2から順に試し、各素因数qについて r^((n-1)/q) mod n が1にならないことを確認します。すべての素因数で条件を満たす最小のrが原始根となります。

このアルゴリズムの時間計算量は、素因数の個数をkとすると、各候補についてk回のべき乗計算が必要なため、全体として非常に効率的に動作します。原始根は暗号理論（Diffie-Hellman鍵交換など）でも重要な概念なので、この実装方法は覚えておくと役立ちます。