アルゴリズム

[Python] 原始根の探索を行うプログラムの実装方法

2025-04-15更新日: 2025-04-15

原始根は、ある素数 $p$ に対して、その整数 $g$ が $p$ の原始根であるためには、 $g^{k} \mod p$ が $1 \leq k < p$ のすべての $k$ に対して異なる値を取る必要があります。

Pythonで原始根を探索するには、まず素数 $p$ のオイラーのトーシェント関数 $ϕ (p) = p - 1$ の約数を求め、各約数に対して $g^{d} \mod p$ が 1 になるかを確認します。

目次から探す

原始根とは何か
Pythonでの原始根探索の基本的な考え方
原始根探索アルゴリズムの実装
効率的な原始根探索のための最適化
応用例：原始根を使った暗号技術
まとめ

原始根とは何か

原始根とは、特定の素数 $p$ に対して、 $p$ のすべての整数の冪を生成することができる整数のことを指します。

具体的には、整数 $g$ が原始根であるためには、次の条件を満たす必要があります。

すなわち、 $g^{k} \mod p$ が $1$ になるのは $k = 0$ のときだけであり、 $k$ は $1$ から $p - 1$ までの整数です。

原始根は数論や暗号理論において重要な役割を果たし、特に離散対数問題や公開鍵暗号の基盤となっています。

原始根を利用することで、効率的な計算や安全な通信が可能になります。

Pythonでの原始根探索の基本的な考え方

素数 $p$ に対する原始根の条件

原始根 $g$ が存在するためには、素数 $p$ に対して次の条件を満たす必要があります。

具体的には、 $g$ が原始根であるためには、次の式が成り立つ必要があります。

$gcd (g^{k} \mod p, p) = 1$

ここで、 $k$ は $1$ から $p - 1$ までの整数です。

この条件を満たす $g$ が存在する場合、 $g$ は $p$ の原始根となります。

原始根は、全ての整数の冪を生成するため、数論的な性質を持つ重要な数です。

オイラーのトーシェント関数の計算

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

素数 $p$ に対しては、次のように計算されます。

$ϕ (p) = p - 1$

この関数は原始根の探索において重要であり、原始根の候補を絞り込む際に利用されます。

具体的には、 $g$ が原始根であるためには、 $g$ の冪が $ϕ (p)$ の約数である必要があります。

素数の約数を求める方法

原始根を探索する際には、オイラーのトーシェント関数の値 $ϕ (p)$ の約数を求める必要があります。

約数を求めるための基本的な方法は、次のように実装できます。

def get_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return divisors
# 使用例
p = 7  # 素数
phi_p = p - 1  # オイラーのトーシェント関数
divisors = get_divisors(phi_p)
print(divisors)

[1, 6, 2, 3]

このコードは、与えられた整数 $n$ の約数をリストとして返します。

原始根の探索においては、 $ϕ (p)$ の約数を求めることで、次のステップに進むことができます。

Pythonでのモジュラ演算の基礎

モジュラ演算は、整数の剰余を計算する演算であり、原始根の探索において非常に重要です。

Pythonでは、モジュラ演算を簡単に行うことができます。

基本的なモジュラ演算の例を以下に示します。

# モジュラ演算の例
a = 5
b = 3
p = 7
result = (a ** b) % p
print(result)

６

このコードは、 $5^{3} \mod 7$ の結果を計算しています。

モジュラ演算を利用することで、原始根の候補を効率的に検証することが可能になります。

原始根探索アルゴリズムの実装

アルゴリズムの概要

原始根を探索するアルゴリズムは、以下のステップで構成されます。

素数 $p$ を入力として受け取る。
オイラーのトーシェント関数 $ϕ (p)$ を計算する。
$ϕ (p)$ の約数を求める。
各候補 $g$ に対して、原始根の条件を満たすか検証する。
条件を満たす $g$ を見つけたら、それを原始根として返す。

このアルゴリズムは、効率的に原始根を見つけるための基本的な手法です。

素数 $p$ の入力と検証

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

以下はその実装例です。

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True
# 使用例
p = int(input("素数を入力してください: "))
if is_prime(p):
    print(f"{p} は素数です。")
else:
    print(f"{p} は素数ではありません。")

素数を入力してください: 7
7 は素数です。

このコードは、入力された数が素数かどうかを判定します。

オイラーのトーシェント関数の計算方法

次に、オイラーのトーシェント関数を計算する関数を実装します。

素数 $p$ に対しては、次のように計算できます。

def euler_totient(p):
    return p - 1
# 使用例
p = 7
phi_p = euler_totient(p)
print(f"オイラーのトーシェント関数 φ({p}) = {phi_p}")

オイラーのトーシェント関数 φ(7) = 6

約数に対する検証ループの実装

オイラーのトーシェント関数の値 $ϕ (p)$ の約数を求め、その約数に対して原始根の条件を検証します。

以下はその実装例です。

def get_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return divisors
def euler_totient(p):
    return p - 1
# 使用例
p = 7
phi_p = euler_totient(p)
divisors = get_divisors(phi_p)
print(f"φ({p}) の約数: {divisors}")

φ(7) の約数: [1, 6, 2, 3]

原始根の候補を探索する方法

原始根の候補を探索するためには、各候補 $g$ に対して、約数に基づいて条件を検証します。

以下はその実装例です。

def is_primitive_root(g, p, phi_p, divisors):
    # g^phi_p ≡ 1 (mod p) であることを確認
    if pow(g, phi_p, p) != 1:
        return False
    # 真の約数に対して g^d ≠ 1 (mod p) であることを確認
    for d in divisors:
        if pow(g, d, p) == 1:
            return False
    return True

def get_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return divisors

def euler_totient(p):
    return p - 1

p = 7
phi_p = euler_totient(p)
divisors = get_divisors(phi_p)
divisors.remove(phi_p)  # φ(p) 自体は除外

# 原始根の候補を探索
for g in range(2, p):  # 1は自明に1のべき乗なので除外
    if is_primitive_root(g, p, phi_p, divisors):
        print(f"{g} は {p} の原始根です。")
        break

3 は 7 の原始根です。

実装例：Pythonコードの解説

上記のコードを組み合わせることで、原始根を探索する完全なプログラムが完成します。

以下はその全体の実装例です。

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def euler_totient(p):
    return p - 1

def get_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    return divisors

def is_primitive_root(g, p, phi_p, divisors):
    # g^phi_p ≡ 1 (mod p) であることを確認
    if pow(g, phi_p, p) != 1:
        return False
    # 真の約数に対して g^d ≠ 1 (mod p) であることを確認
    for d in divisors:
        if pow(g, d, p) == 1:
            return False
    return True

# メインプログラム
p = int(input("素数を入力してください: "))
if is_prime(p):
    phi_p = euler_totient(p)
    divisors = get_divisors(phi_p)
    divisors.remove(phi_p)  # φ(p) 自体は除外
    for g in range(2, p):
        if is_primitive_root(g, p, phi_p, divisors):
            print(f"{g} は {p} の原始根です。")
            break
else:
    print(f"{p} は素数ではありません。")

このプログラムは、ユーザーから素数を入力として受け取り、その素数の原始根を探索します。

原始根が見つかると、その値を出力します。

効率的な原始根探索のための最適化

素数判定の効率化

素数判定は、原始根探索において重要なステップですが、特に大きな数に対しては計算コストが高くなります。

効率的な素数判定の方法として、以下のアルゴリズムが考えられます。

エラトステネスの篩: 小さな素数を事前に計算し、これを用いて素数判定を行う。
ミラー・ラビン素数判定法: 確率的な方法で、非常に大きな数に対しても効率的に素数判定が可能です。

以下は、ミラー・ラビン法を用いた素数判定の実装例です。

import random
def miller_rabin(n, k=5):  # kは試行回数
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True
# 使用例
p = 31
print(f"{p} は素数ですか？ {miller_rabin(p)}")

31 は素数ですか？ True

約数の計算を高速化する方法

約数の計算を高速化するためには、以下の方法が有効です。

平方根までの探索: 約数は対になっているため、 $n$ の平方根まで探索すれば十分です。
事前計算: よく使う数の約数を事前に計算しておくことで、再利用が可能です。

以下は、平方根までの探索を用いた約数計算の実装例です。

def get_divisors_fast(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(divisors)
# 使用例
phi_p = 12
divisors = get_divisors_fast(phi_p)
print(f"φ({phi_p}) の約数: {divisors}")

φ(12) の約数: [1, 2, 3, 4, 6, 12]

メモ化による計算の最適化

メモ化は、計算結果をキャッシュすることで、同じ計算を繰り返さないようにする手法です。

特に、オイラーのトーシェント関数や約数計算において、メモ化を利用することで効率を大幅に向上させることができます。

以下は、メモ化を用いたオイラーのトーシェント関数の実装例です。

from functools import lru_cache
@lru_cache(maxsize=None)
def euler_totient_memo(n):
    if n == 1:
        return 1
    result = n
    p = 2
    while p * p <= n:
        if n % p == 0:
            while n % p == 0:
                n //= p
            result -= result // p
        p += 1
    if n > 1:
        result -= result // n
    return result
# 使用例
print(f"φ(10) = {euler_totient_memo(10)}")

φ(10) = 4

大きな素数に対する原始根探索の工夫

大きな素数に対する原始根探索では、以下の工夫が有効です。

並列処理: 複数の候補を同時に検証することで、計算時間を短縮します。
バッチ処理: 複数の素数に対して一度に原始根を探索することで、計算のオーバーヘッドを減少させます。
効率的なデータ構造: 候補を管理するために、ヒープやセットを利用することで、探索を効率化します。

これらの工夫を組み合わせることで、大きな素数に対する原始根探索をより効率的に行うことが可能になります。

応用例：原始根を使った暗号技術

Diffie-Hellman鍵交換における原始根の役割

Diffie-Hellman鍵交換は、二者間で安全に共通の秘密鍵を生成するためのプロトコルです。

このプロトコルでは、原始根が重要な役割を果たします。

具体的には、以下の手順で原始根が利用されます。

参加者は、素数 $p$ とその原始根 $g$ を共有します。
各参加者は、自分の秘密の整数 $a$ と $b$ を選び、それぞれ $A = g^{a} \mod p$ と $B = g^{b} \mod p$ を計算します。
参加者は、計算した値 $A$ と $B$ を交換します。
最後に、各参加者は相手の値を使って共通の秘密鍵を計算します。