×

Cài đặt thuật toán Miller-Rabin Primality Test trong lập trình

Avatar of admin
admin 4 Views

Thuật toán Miller-Rabin là một trong những thuật toán kiểm tra tính nguyên tố hiệu quả nhất, đặc biệt là trong trường hợp các số lớn. Phương pháp này được đánh giá cao do độ chính xác và tốc độ xử lý của nó. Dưới đây là cách cài đặt thuật toán Miller-Rabin kiểm tra tính nguyên tố trong ngôn ngữ lập trình Python.

Hiểu về thuật toán Miller-Rabin

Thuật toán Miller-Rabin là một thuật toán xác suất, nghĩa là nó có thể không chính xác 100% với mọi số kiểm tra, nhưng khả năng xảy ra lỗi là rất nhỏ và có thể giảm thiểu bằng cách tăng số lần kiểm tra. Cơ bản, thuật toán này dựa trên lý thuyết số học và phép lũy thừa mô-đun.

Các bước của thuật toán:

  1. Phân tích số cần kiểm tra: Viết số n - 1 dưới dạng $2^s \times d$ với d là số lẻ.
  2. Lặp lại nhiều lần kiểm tra:
    • Chọn ngẫu nhiên một cơ số a.
    • Tính $x = a^d \mod n$
    • Nếu x là 1 hoặc n - 1, n có thể là số nguyên tố.
    • Nếu không, lặp lại tính $a^{2^r \times d} \mod n$ cho $0 \le r \le s - 1$. Nếu không tồn tại r nào làm giá trị x bằng n - 1, n là hợp số.

Cài đặt trong Python

Đầu tiên, chúng ta cần một hàm để thực hiện phép lũy thừa mô-đun, và một hàm để kiểm tra n thành phần của n - 1.

import random

def power_mod(base, exponent, mod):
    result = 1
    base = base % mod
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % mod
        exponent = exponent >> 1
        base = (base * base) % mod
    return result

def miller_rabin(n, k):
    # Trường hợp đặc biệt
    if n in (2, 3):
        return True
    if n <= 1 or n % 2 == 0:
        return False
    
    # Phân tích n-1 dưới dạng 2^s * d
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    
    # Thực hiện k lần kiểm tra
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = power_mod(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = power_mod(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

# Hàm kiểm tra nhanh gọn
def is_prime(n, k=5):
    return miller_rabin(n, k)

# Ví dụ kiểm tra
if __name__ == "__main__":
    n = int(input("Nhập số cần kiểm tra: "))
    if is_prime(n):
        print(f"{n} là số nguyên tố.")
    else:
        print(f"{n} không phải là số nguyên tố.")

Chi tiết triển khai

  • Hàm power_mod: Thực hiện tính lũy thừa mô-đun, giúp tính các giá trị như $a^d \mod n$ một cách hiệu quả.
  • Hàm miller_rabin: Thực hiện kiểm tra Miller-Rabin với nhiều lần kiểm tra (k), giảm thiểu khả năng sai sót xác suất.
  • Hàm is_prime: Hàm chính để kiểm tra số nguyên tố, gọi hàm miller_rabin với số lần kiểm tra mặc định.

Tổng kết

Cài đặt thuật toán Miller-Rabin trong Python không chỉ giúp kiểm tra tính nguyên tố của các số lớn một cách hiệu quả và nhanh chóng mà còn cung cấp một ví dụ rõ ràng về cách sử dụng lý thuyết số học trong lập trình. Viet những dòng code này có thể cải thiện rất nhiều hiệu suất khi làm việc với các dự án liên quan tới số học và mật mã học.

Comments

Bài viết liên quan