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

a^{n-1}\ \equiv\ 1 \pmod n

a^{({n-1})/q}\ \not\equiv\ 1 \pmod 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:

11^{70}\ \equiv\ 1 \pmod {71}

Đ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ó:

11^{35}\ \equiv\ 70\ \not\equiv\ 1 \pmod {71}
11^{14}\ \equiv\ 54\ \not\equiv\ 1 \pmod {71}
11^{10}\ \equiv\ 32\ \not\equiv\ 1 \pmod {71}

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]