Kiểm tra Lucas-Lehmer

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Bài này nói về kiểm tra Lucas–Lehmer tính nguyên tố cho trường hợp tổng quát. Còn có Kiểm tra Lucas-Lehmer cho số Mersenne.

Trong số học cho máy tính (hay số học thuật toán), kiểm tra Lucas–Lehmer là phép kiểm tra tính nguyên tố đối với số tự nhiên n; nó đòi hỏi rằng có một thừa số nguyên tố của n − 1 là đã biết.

Nếu tồn tại số a nhỏ hơn n và lớn hơn 1 là số thoả mãn

với mọi ước nguyên tố qcủa n − 1, thì n là số nguyên tố. Nếu không tìm thấy số a như vậy thì n là hợp số.

Chẳng hạn, với n = 71, n − 1 = 70 = (2)*(5)*(7). Lấy a = 11 trước hết:

Điều này cho thấy bậc của 11 mod 71 là 70 vì ước của 70 chỉ có thể như trên. Nhưng kiểm tra với các ước của 70 ta có:

Do đó bậc của 11 mod 71 là 70, và như vậy 71 là số nguyên tố.

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]