Thuật toán Miller-Rabin trong Python

Học sinh phấn khởi học lập trình

Thuật toán Miller-Rabin là một thuật toán xác định tính nguyên tố của một số nguyên dương. Thuật toán này được đặt theo tên của các nhà toán học Gary L. Miller và Michael O. Rabin, người đã công bố nó vào năm 1980.

Thuật toán Miller-Rabin dựa trên một kỹ thuật gọi là “kiểm tra nguyên tố không chính xác”. Ý tưởng cơ bản của thuật toán là kiểm tra xem một số nguyên dương n có phải là nguyên tố hay không bằng cách chọn ngẫu nhiên một số nguyên a và kiểm tra một số điều kiện liên quan đến tính chất của số nguyên n.

Dưới đây là thuật toán Miller-Rabin để kiểm tra xem một số n có phải là nguyên tố hay không:

  1. Đặt số nguyên dương n – 1 = 2^r * m với một số lẻ m.
  2. Chọn một số nguyên a ngẫu nhiên từ khoảng [2, n – 2].
  3. Tính giá trị x_0 = a^m mod n.
  4. Với i từ 0 đến r – 1, tính giá trị x_i+1 = (x_i^2) mod n.
  5. Nếu tồn tại một số i trong khoảng từ 0 đến r – 1 mà x_i là bằng 1 và x_i-1 khác 1 và n – 1, thì số n không phải là số nguyên tố.
  6. Nếu x_r không bằng 1, số n cũng không phải là số nguyên tố.
  7. Nếu không thỏa mãn các điều kiện trên, số n có khả năng lớn là số nguyên tố.

Thuật toán Miller-Rabin có độ phức tạp thời gian O(k * log n), trong đó k là số lần kiểm tra. Với mỗi lần kiểm tra, thuật toán sử dụng phép tính modulo và lũy thừa modulo để tính toán giá trị x_i. Khi số lượng lần kiểm tra tăng lên, độ chính xác của thuật toán cũng tăng.

Tuy thuật toán Miller-Rabin không đảm bảo xác định tính nguyên tố của một số, nhưng với số lần kiểm tra đủ lớn, nó cho kết quả chính xác đối với hầu hết các số nguyên dương.

Dưới đây là một cài đặt đơn giản của thuật toán Miller-Rabin bằng Python:

import random

def is_prime(n, k):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    r, m = 0, n - 1
    while m % 2 == 0:
        r += 1
        m //= 2

    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, m, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False

    return True

# Sử dụng hàm is_prime để kiểm tra tính nguyên tố của một số
n = 37
k = 5  # Số lần kiểm tra, có thể điều chỉnh tùy ý

if is_prime(n, k):
    print(f"{n} là số nguyên tố")
else:
    print(f"{n} không là số nguyên tố")

Trong đoạn mã trên, hàm is_prime nhận đầu vào là số nguyên dương n cần kiểm tra và số lần kiểm tra k. Đầu tiên, chúng ta kiểm tra các trường hợp đặc biệt khi n là 0, 1, 2 hoặc 3. Sau đó, ta tìm giá trị rm sao cho n - 1 = 2^r * m, với m là một số lẻ.

Tiếp theo, ta thực hiện k lần kiểm tra. Trong mỗi lần kiểm tra, ta chọn ngẫu nhiên một số a từ khoảng [2, n – 2]. Ta tính giá trị x = a^m mod n và kiểm tra xem x có bằng 1 hoặc n - 1 không. Nếu không thỏa mãn điều kiện này, ta tiếp tục tính x = x^2 mod n r - 1 lần và kiểm tra xem x có bằng n - 1 không. Nếu tất cả các lần kiểm tra đều không thỏa mãn, ta kết luận n không là số nguyên tố.

Cuối cùng, ta sử dụng hàm is_prime để kiểm tra tính nguyên tố của số n được chọn. Bạn có thể thay đổi giá trị của nk để thử nghiệm với các số khác nhau.

Ví dụ: Tìm dãy số nguyên tố từ 1 đến n với thuật toán trên

Để tìm dãy số nguyên tố từ 1 đến một giá trị nguyên dương n sử dụng thuật toán Miller-Rabin, bạn có thể áp dụng thuật toán kiểm tra tính nguyên tố cho từng số trong khoảng [1, n]. Dưới đây là một ví dụ cài đặt để tìm dãy số nguyên tố từ 1 đến n:

import random

def is_prime(n, k):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    r, m = 0, n - 1
    while m % 2 == 0:
        r += 1
        m //= 2

    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, m, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False

    return True

def find_prime_sequence(n, k):
    prime_sequence = []
    for i in range(1, n + 1):
        if is_prime(i, k):
            prime_sequence.append(i)
    return prime_sequence

# Sử dụng hàm find_prime_sequence để tìm dãy số nguyên tố từ 1 đến n
n = 100
k = 5  # Số lần kiểm tra, có thể điều chỉnh tùy ý

prime_sequence = find_prime_sequence(n, k)
print("Dãy số nguyên tố từ 1 đến", n, "là:", prime_sequence)

Trong ví dụ trên, hàm find_prime_sequence nhận đầu vào là giá trị nguyên dương n và số lần kiểm tra k. Hàm này sử dụng hàm is_prime để kiểm tra tính nguyên tố của từng số trong khoảng từ 1 đến n. Nếu một số là số nguyên tố, nó được thêm vào danh sách prime_sequence.

Cuối cùng, chúng ta sử dụng hàm find_prime_sequence để tìm dãy số nguyên tố từ 1 đến n với giá trị nk đã cho. Kết quả sẽ được in ra màn hình.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *