アルゴリズム

[C言語] 原始根の計算と応用方法

2025-01-17更新日: 2025-01-17

C言語で原始根を計算するには、まず与えられた素数 $p$ に対して、1から $p - 1$ までの整数が生成するサイクルの長さが $p - 1$ になる整数を見つける必要があります。

これには、オイラーの定理やフェルマーの小定理を利用して、各候補の整数 $g$ に対して $g^{k} \mod p \neq 1$ となる $k$ が $p - 1$ のすべての素因数に対して存在するかを確認します。

原始根は暗号理論やディジタル署名、公開鍵暗号のアルゴリズムで重要な役割を果たします。

特に、ディフィー・ヘルマン鍵交換やRSA暗号などで、数論的な性質を利用して安全な通信を実現するために用いられます。

目次から探す

原始根とは何か
C言語での原始根の計算方法
原始根の応用例
C言語での原始根計算の最適化
まとめ

原始根とは何か

原始根の定義

原始根とは、数論において特定の整数に対して、その整数のべき乗を取ることで、すべての整数を生成できる数のことを指します。

具体的には、ある素数 $p$ に対して、整数 $g$ が原始根であるとは、 $g^{1}, g^{2}, \dots, g^{p - 1}$ がすべて異なる剰余を持ち、1から $p - 1$ までのすべての整数を生成することを意味します。

数論における原始根の重要性

原始根は数論において非常に重要な役割を果たします。

特に、以下のような分野でその重要性が際立ちます。

暗号理論: 原始根は、ディフィー・ヘルマン鍵交換やRSA暗号などの暗号アルゴリズムにおいて、鍵生成や暗号化の基盤として利用されます。
擬似乱数生成: 原始根を利用することで、周期性の高い擬似乱数を生成することが可能です。
数論的関数の計算: 原始根を用いることで、オイラーのトーシェント関数やその他の数論的関数の計算が効率的に行えます。

原始根の存在条件

原始根が存在するための条件は、以下の通りです。

素数 $p$ : 任意の素数 $p$ に対して、必ず原始根が存在します。
素数のべき乗 $p^{k}$ : 素数のべき乗に対しても原始根が存在します。
2と4: これらの数に対しても原始根が存在します。
2のべき乗 $2^{k}$ (k \geq 3): この場合も原始根が存在します。

これらの条件を満たす整数に対して、原始根を見つけることが可能です。

原始根の存在は、数論の基本定理やオイラーの定理を用いて証明されます。

C言語での原始根の計算方法

必要な数学的知識

オイラーの定理

オイラーの定理は、任意の整数 $a$ と互いに素な整数 $n$ に対して、次の式が成り立つことを示しています。

$a^{ϕ (n)} \equiv 1 (\mod n)$

ここで、 $ϕ (n)$ はオイラーのトーシェント関数で、 $n$ 以下の整数のうち、 $n$ と互いに素な数の個数を表します。

この定理は、原始根の計算において、数のべき乗を効率的に計算するために利用されます。

フェルマーの小定理

フェルマーの小定理は、素数 $p$ に対して、任意の整数 $a$ が次の式を満たすことを示しています。

$a^{p - 1} \equiv 1 (\mod p)$

この定理は、原始根の検証において、数が特定の条件を満たすかどうかを確認するために使用されます。

アルゴリズムの概要

原始根を計算するためのアルゴリズムは、以下の手順で進めます。

素数 $p$ を入力として受け取る。
$p - 1$ の素因数を求める。
各整数 $g$ を候補として、 $g^{(p - 1) / q} ≢ 1 (\mod p)$ をすべての素因数 $q$ に対して確認する。
条件を満たす最小の $g$ を原始根とする。

C言語での実装手順

素数の入力と検証

まず、ユーザーから素数を入力として受け取り、その数が本当に素数であるかを確認します。

#include <stdio.h>
#include <stdbool.h>
// 素数判定関数
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

原始根の候補生成

次に、原始根の候補となる整数を生成します。

// 原始根の候補生成
int findPrimitiveRoot(int p) {
    for (int g = 2; g < p; g++) {
        if (isPrimitiveRoot(g, p)) {
            return g;
        }
    }
    return -1; // 原始根が見つからない場合
}

原始根の検証

候補となる整数が実際に原始根であるかを検証します。

#include <math.h>
// 原始根の検証
bool isPrimitiveRoot(int g, int p) {
    int phi = p - 1;
    for (int q = 2; q <= sqrt(phi); q++) {
        if (phi % q == 0) {
            if (powerMod(g, phi / q, p) == 1) {
                return false;
            }
        }
    }
    return true;
}
// モジュラ指数計算
int powerMod(int base, int exp, int mod) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

完成したプログラム

以下に、C言語での原始根計算の完成したプログラムを示します。

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
// 素数判定関数
bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
// モジュラ指数計算
int powerMod(int base, int exp, int mod) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}
// 原始根の検証
bool isPrimitiveRoot(int g, int p) {
    int phi = p - 1;
    for (int q = 2; q <= sqrt(phi); q++) {
        if (phi % q == 0) {
            if (powerMod(g, phi / q, p) == 1) {
                return false;
            }
        }
    }
    return true;
}
// 原始根の候補生成
int findPrimitiveRoot(int p) {
    for (int g = 2; g < p; g++) {
        if (isPrimitiveRoot(g, p)) {
            return g;
        }
    }
    return -1; // 原始根が見つからない場合
}
int main() {
    int p;
    printf("素数を入力してください: ");
    scanf("%d", &p);
    if (!isPrime(p)) {
        printf("%d は素数ではありません。\n", p);
        return 1;
    }
    int primitiveRoot = findPrimitiveRoot(p);
    if (primitiveRoot != -1) {
        printf("%d の原始根は %d です。\n", p, primitiveRoot);
    } else {
        printf("%d の原始根は見つかりませんでした。\n", p);
    }
    return 0;
}

素数を入力してください: 7
7 の原始根は 3 です。

このプログラムは、ユーザーが入力した素数に対して原始根を計算し、結果を表示します。

入力が素数でない場合は、エラーメッセージを表示します。

原始根の応用例

暗号理論における利用

原始根は、暗号理論において重要な役割を果たします。

特に、鍵交換や暗号化のプロセスにおいて、その特性が活用されます。

ディフィー・ヘルマン鍵交換

ディフィー・ヘルマン鍵交換は、2人のユーザーが安全に共通の秘密鍵を生成するためのプロトコルです。

このプロトコルでは、原始根を利用して、公開鍵と秘密鍵を生成します。

具体的には、次の手順で行われます。

共通の素数 $p$ とその原始根 $g$ を選択します。
各ユーザーは秘密の整数 $a$ と $b$ を選び、それぞれ $A = g^{a} \mod p$ と $B = g^{b} \mod p$ を計算して交換します。
共通の秘密鍵は、 $A^{b} \mod p$ または $B^{a} \mod p$ として計算されます。