Kiểm Tra Số Nguyên Tố Miller-Rabin
Kiểm tra nguyên tố Miller-Rabin
Trong dịp lễ kỷ niệm 1024 dành cho lập trình viên năm nay, công ty tổ chức một buổi chia sẻ kiến thức, và tôi đã trình bày về chủ đề tối ưu hóa thuật toán. Trong đó, tôi nhấn mạnh rằng việc cải tiến logic của thuật toán thường hiệu quả hơn nhiều so với việc tối ưu hóa cú pháp code thông thường. Một ví dụ tôi nêu ra là bài toán kiểm tra tính nguyên tố của một số nguyên.
Phương pháp kiểm tra nguyên tố cổ điển như chia thử từng số nhỏ hơn căn bậc hai của số cần kiểm tra thường rất chậm với các số lớn. Trong khi đó, kiểm tra Miller-Rabin lại có tốc độ vượt trội hàng chục nghìn lần hoặc hơn, đặc biệt với số có hàng trăm chữ số. Tôi chia sẻ rằng thực chất cơ sở lý thuyết của thuật toán này không quá phức tạp, thậm chí học sinh cấp 3 với kiến thức toán phổ thông cũng có thể hiểu được, không cần đến các công thức toán cao cấp.
Sau buổi thuyết trình, một bạn trẻ thắc mắc rằng liệu học sinh thật sự có thể hiểu được bài giải thích trên Wikipedia về chủ đề này. Tôi đọc lại tài liệu và nhận thấy rằng rào cản lớn nhất chính là các thuật ngữ chuyên ngành như “modulo”, “số giả nguyên tố” hay “chứng minh phản chứng” – những khái niệm ít xuất hiện trong sách giáo khoa phổ thông. Về mặt bản chất, logic của thuật toán lại khá trực quan. Ngoài ra, phiên bản tiếng Việt trên Wikipedia được trình bày chưa thực sự rõ ràng, khiến người đọc dễ bị lạc trong rừng ký hiệu.
Từ cơ bản đến hiện đại
Cách kiểm tra nguyên tố đơn giản nhất là dựa vào định nghĩa: Thử chia số cần kiểm tra (gọi là p) cho tất cả các số nguyên từ 2 đến √p. Nếu không phép chia nào có số dư bằng 0, thì p là số nguyên tố. Tuy nhiên, ta có thể tối ưu bằng cách chỉ thử với các số nguyên tố nhỏ hơn √p, hoặc loại bỏ các số chẵn (ngoại trừ 2).
Một bước tiến mới đến từ Định lý nhỏ Fermat: Với p là số nguyên tố, bất kỳ số nguyên a nào không chia hết cho p đều thỏa mãn:
a^(p-1) ≡ 1 (mod p)
Điều này mở ra hướng kiểm tra ngẫu nhiên: Chọn ngẫu nhiên a, nếu a^(p-1) mod p ≠ 1 thì p chắc chắn không nguyên tố. Nếu bằng 1, p có thể là nguyên tố với xác suất nhất định. Càng thử nhiều a, xác suất p đúng nguyên tố càng cao.
Tuy nhiên, phương pháp này vẫn tồn tại lỗi với các số giả nguyên tố (ví dụ: Số Carmichael 561 = 3×11×17). Để khắc phục, kiểm tra Miller-Rabin đưa ra quy trình kiểm tra nghiêm ngặt hơn, dựa trên phân tích chi tiết các phương trình đồng dư.
Cơ chế của Miller-Rabin
Giả sử p là số nguyên tố lẻ, ta viết p-1 = 2^s × d (với d là số lẻ). Khi đó, với mọi a ∈ [2, p-1], một trong hai điều kiện sau phải đúng:
- a^d ≡ 1 (mod p), hoặc
- Tồn tại r ∈ [0, s-1] sao cho a^(2^r × d) ≡ -1 (mod p)
Ngược lại, nếu p là hợp số, sẽ tồn tại một số a (gọi là “chứng nhân”) không thỏa mãn cả hai điều kiện trên. Thuật toán sẽ thử nhiều giá trị a ngẫu nhiên:
- Nếu tìm được chứng nhân → p chắc chắn là hợp số.
- Nếu không tìm thấy → p là số nguyên tố với xác suất rất cao.
Tối ưu hóa trong thực tế
Một điểm thú vị của Miller-Rabin là tập hợp các chứng nhân tối ưu đã được xác định cho các khoảng số cụ thể. Ví dụ:
- Với p < 2^32, chỉ cần kiểm tra với a ∈ {2, 7, 61}.
- Với p < 2^64, tập hợp {2, 3, 5, 7, 11, 13, 17} là đủ.
Điều này biến thuật toán xác suất thành phương pháp chắc chắn trong các ứng dụng thực tế như mật mã RSA. Một cải tiến gần đây còn kết hợp hàm băm để chia nhỏ không gian số cần kiểm tra, từ đó giảm số lần kiểm tra xuống còn 1-2 lần cho các số 32-bit.
Chứng minh trực quan
Để hiểu tại sao điều kiện trên đúng, ta bắt đầu từ định lý Fermat: a^(p-1) ≡ 1 (mod p). Khi p là nguyên tố, p-1 là số chẵn, ta có thể viết a^(p-1) = (ad)2s. Bằng cách liên tục khai căn bậc hai, ta sẽ đến ad ≡ ±1 (mod p). Nếu không xuất hiện ±1 ở bất kỳ bước nào, p phải là hợp số.
Một ví dụ điển hình là p = 15:
- a = 4 → 414 ≡ 1 (mod 15), nhưng 4(2×7) ≡ 4^2 ≡ 1 (mod 15).
- Tuy nhiên, 15 = 3×5 không phải nguyên tố, cho thấy cách tiếp cận của Fermat chưa đủ.
Kết luận
Miller-Rabin kết hợp giữa lý thuyết số học thuần túy và tư duy tin học thông minh. Nó không chỉ là công cụ kiểm tra nguyên tố hiệu quả, mà còn là minh chứng cho sự giao thoa giữa toán học và khoa học máy tính. Với những ai