Pythonで素数判定しよう！（中級編）

こんばんは。学びの探求者です。

基礎編、基礎編＋では、簡単な素数の判定をPythonで実行してみました。

素数は、暗号など私たちの生活で大変重要な場面で活用されているので、多くの研究がなされていますので、実は、Pythonに素数判定のライブラリーがあるんです。

そこで、今回はそのライブラリーを使って、素数判定をしてみましょう。

sympy.isprime の紹介

sympyはPythonの代数計算のライブラリーです。
その中でも、isprimeは整数が素数がどうかを判定する関数です。

Number Theory - SymPy 1.13.3 documentation

では、適当な10桁の整数「4036134689」が素数かどうかを判定するコードをご紹介します。

コード

from sympy import isprime

num = 4036134689  # 大きな素数
print(f"{num} は素数ですか？: {isprime(num)}")

はい。これだけです！
ただし、インターネットセキュリティに関わるような暗号で使われる素数は、とても大きな桁の素数を使うため、この判定法は用いられません。

実際には「ミラー・ラビン法」というものを使います。
どういうものなのか簡単にご紹介します。

ミラー・ラビン法とは？

ミラー・ラビン法とは、確率を使った素数判定法です。
これは、素数pと互いに素な自然数α（1 以外に共通の約数を持たない）に対して、2つの条件のいずれかが成り立つというものを利用した手法です。

もう少し大きな20桁の素数「38532517008464397887」が素数かどうかを判定してみましょう。

コード

import random

def is_prime_miller_rabin(n, k=5):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0:
        return False
    
    # n-1 を (2^r) * d の形に分解する
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    # 確率的テストを k 回実施
    for _ in range(k):
        a = random.randint(2, n - 2)  # 2 以上 n-2 以下のランダムな整数を選ぶ
        x = pow(a, d, n)  # a^d % n を計算

        if x == 1 or x == n - 1:
            continue  # テストに合格

        for _ in range(r - 1):  # 2^r 回繰り返す
            x = pow(x, 2, n)
            if x == n - 1:
                break  # テストに合格
        else:
            return False  # 合格しなかったら合成数と判定
    return True  # すべてのテストに合格したら素数と判定

num = 38532517008464397887  # 大きな素数
print(f"{num} は素数ですか？: {is_prime_miller_rabin(num)}")

結果

38532517008464397887 は素数ですか？: True

ミラー・ラビン法は確率的なアルゴリズムなので、テストの回数kの値を大きくすればするほど、誤判定の確率が減る仕組みになっています。
今回は、20桁の数値なので k=5 回でも正しく判定できたようです。
また、このコードの中で重要なポイントとして以下の点が挙げられます：

• random.randint(2, n - 2) は、テスト用の a をランダムに選ぶ部分です。

• pow(a, d, n) は a^d % n を計算する Python の組み込み関数で、効率的な累乗剰余計算ができるため、大きな数でも高速に処理できます。

まとめ

sympy.isprime は学習用途や小さなプロジェクトに便利ですが、実務で使うにはさらなる工夫が必要です。

次回は、RSA暗号など、実際にどのように素数が利用されているのかを掘り下げます。お楽しみに！