Kiểm tra Lucas-Lehmer

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới 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]