確率的素数判定 (フェルマーテスト)
(NumberTheory/Prime/fermat_test.py)

• View this file on GitHub
• Last update: 1970-01-01 00:00:00+00:00

概要

フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズム。

フェルマーの小定理

素数 $p$ と互いに素な整数 $a$ に対して、

\[a^{p-1} \equiv 1 \pmod{p}\]

が成り立つ。

フェルマーの小定理の対偶

整数 $n$ と互いに素な整数 $a$ に対して、

\[a^{n-1} \not\equiv 1 \pmod{n}\]

であるならば $n$ は合成数。

フェルマーテストでは、$n$ と互いに素な整数 $a$ をランダムに選び、$a^{n-1} \not\equiv 1 \pmod{n}$ ならば $n$ を合成数、$a^{n-1} \equiv 1 \pmod{n}$ ならば $n$ を確率的素数と判定する。

擬素数

素数ではないにもかかわらず確率的素数と判定される合成数を擬素数という。例えば $n = 341$、$a = 2$ に対して

\[2^{340} \equiv 1 \pmod{341}\]

となる。この場合、$341$ は素数ではない ($341 = 11 × 3$) にもかかわらず確率的素数と判定される。

カーマイケル数

複数の $a$ に対してフェルマーテストを行うことで、素数判定の正確度を向上させる。 例えば $n = 341$、$a = 5$ に対して

\[5^{340} \equiv 67 \not\equiv 1 \pmod{341}\]

となるので、この場合は $341$ を合成数と判定できる。しかしながら、すべての $a$ に対してフェルマーテストを通過する合成数が存在し、これをカーマイケル数という。カーマイケル数は小さい方から $561, 1105, 1729, \dots$ であり、無数に存在する (OEIS A002997)。

使い方

fermat_test(n: int) -> bool
n の確率的素数判定結果 (True: 素数である、False: 素数ではない) を返す。カーマイケル数は素数ではないにもかかわらず必ず True を返すので注意。計算量 $O(\log n)$

Code

import random


def fermat_test(n, rep=100):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    if n == 1:
        return False
    if n == 2:
        return True
    for _ in range(rep):
        a = random.randint(2, n - 1)
        if gcd(a, n) != 1:
            # a と n が互いに素ではない時点で n は合成数
            # カーマイケル数を素数と誤判定させるために continue している
            continue
        if pow(a, n - 1, n) != 1:
            return False
    return True

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page