ミラー・ラビン素数判定法
(library/math/miller_rabin.py)

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

Verified with

• tests/math/miller-rabin/libchecker.test.py

Code

from typing import List


def millar_rabin_test(n: int) -> bool:
    if n < 2:
        return False
    if n & 1 == 0:
        return n == 2
    d = n - 1
    s = 0
    while d & 1 == 0:
        d >>= 1
        s += 1
    assert d & 1 == 1

    def test(a: int) -> bool:
        x = pow(a, d, n)
        if x == 0:
            return False
        if x == 1:
            return True
        for _ in range(s):
            y = x * x % n
            if y == 1 and x != 1 and x != n - 1:
                return False
            x = y
        return x == 1

    def tests(basis: List[int]) -> bool:
        return all(test(a) for a in basis)


    if n < 2_047:
        return test(2)
    if n < 1_373_653:
        return tests([ 2, 3 ])
    if n < 9_080_191:
        return tests([ 31, 73 ])
    if n < 25_326_001:
        return tests([ 2, 3, 5 ])
    if n < 3_215_031_751:
        return tests([ 2, 3, 5, 7 ])
    if n < 4_759_123_141:
        return tests([ 2, 7, 61 ])
    if n < 1_122_004_669_633:
        return tests([ 2, 13, 23, 1662803 ])
    if n < 2_152_302_898_747:
        return tests([ 2, 3, 5, 7, 11 ])
    if n < 3_474_749_660_383:
        return tests([ 2, 3, 5, 7, 11, 13 ])
    if n < 341_550_071_728_321:
        return tests([ 2, 3, 5, 7, 11, 13, 17 ])
    if n < 3_825_123_056_546_413_051:
        return tests([ 2, 3, 5, 7, 11, 13, 17, 19, 23 ])
    if n <= 18_446_744_073_709_551_615:
        return tests([ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ])

    raise ValueError("n is too large (>= 2**64)")

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.2/x64/lib/python3.13/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.13.2/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page