Kiểm tra Lucas-Lehmer
Bách khoa toàn thư mở Wikipedia
- 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 áp dụng cho các 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à
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ố.
