Mô phỏng thuật toán Kiểm tra nguyên tố Miller-Rabin

Miller-Rabin Primality Test · Nhóm: Số học

Kiểm tra nguyên tố Miller-Rabin (Miller-Rabin Primality Test), nhóm Số học.

Mã Python

def is_prime(n, witnesses=(2,3,5,7,11,13)):
    if n < 2: return False
    if n in (2, 3): return True
    if n % 2 == 0: return False
    d, r = n - 1, 0
    while d % 2 == 0:
        d //= 2; r += 1
    for a in witnesses:
        if a >= n: continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1: continue
        for _ in range(r - 1):
            x = x * x % n
            if x == n - 1: break
        else:
            return False
    return True

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.