XÂY DỰNG CHƯƠNG TRèNH KIỂM TRA SỐ NGUYÊN TỐ BẰNG THUẬT TOÁN MILLER- RABIN

MỤC LỤC

CHƯƠNG 1: CƠ SỞ THUẬT TOÁN

CHƯƠNG 2: PHÂN TÍCH VÀ THIẾT KẾ

CHƯƠNG 3: CÀI ĐẶT VÀ KIỂM THỬ

PHỤ LỤC

Chương 1

CƠ SỞ THUẬT TOÁN

1.Giới thiệu

Bài toán kiểm tra số nguyên tố là một trong những bài toán cơ bản nhưng hết sức quan trong trọng lĩnh vực an toàn và bảo mật thụng tin cụ thể là trong hệ mật RSA.Cú rất nhiều phương pháp kiểm tra số nguyờn tố như : phương pháp chứng minh theo định lý Fecma, phương pháp sàng số nguyờn tố Eratosthenes, phương pháp kiểm tra theo xỏc suất. Thuật toỏn Miller- Rabin là thuật toỏn dựa trên phương phỏp chứng minh theo xỏc suất.Thuật toán này được thao tỏc trờn số lớn.

2.Cơ sở thuật toỏn Miller-Rabin

Thuật toán này dựa trên một định lý quan trong sau:

”Nếu n là số nguyên tố thì (n-1 )!≡ (n-1) mod n”.

“Với mỗi số nguyên n, ễ(n) là số các số nguyên tố cùng nhau với n mà nhỏ hơn n. Khi đó, với mọi x, x > 0, xễ(n) ≡ 1 mod n ”.

3.Thuật toán

Sơ đồ thuật toán: