Kiểm tra Fermat

Kiểm tra Fermat là một thuật toán xác suất kiểm tra một số tự nhiên là hợp số hay là số nguyên tố.

Khái niệm

[sửa | sửa mã nguồn]

Định lý nhỏ Fermat phát biểu rằng nếu p là số nguyên tố và , thì

.

Nếu ta muốn kiểm tra số n có là nguyên tố không, ta lấy ngẫu nhiên các số a' và kiểm tra xem đẳng thức trên có đúng không. Nếu nó không đúng với một giá trị a nào đó thì n là hợp số. Nếu đẳng thức đúng với nhiều giá trị của a, ta có thể nói rằng n là số nguyên tố với xác suất nào đó, hay là một số giả nguyên tố (pseudoprime).

Có thể phép thử sẽ cho ta một kết quả sai.

Số a

trong khi n là hợp số được gọi là một giả Fermat.

Còn nếu có số a

thì a được xem như một bằng chứng Fermat chứng tỏ n là hợp số.

Thuật toán và thời gian thi hành

[sửa | sửa mã nguồn]

Thuật toán có thể viết như sau:

Inputs: n: giá trị để kiểm tra tính nguyên tố; k: tham số tham gia vào quá trình kiểm tra
Output: hợp số nếu n là hợp số, nếu không nguyên tố xác suất
repeat k times:
lấy a ngẫu nhiên trong [1, n − 1]
if an − 1 mod n ≠ 1 then
return composite
return probably prime

Khi dùng thuật toán tính nhanh luỹ thừa theo mođun, thời gian thi hành của thuật toán là O(k × log3n), ở đó k là số lần kiểm tra với mỗi số a ngãu nhiên, và n là giá trị ta muốn kiểm tra.

Khả năng vận dụng

[sửa | sửa mã nguồn]

Có khá nhiều giá trị của n là các số Carmichael mà với tất cả các giá trị của a sao cho ƯCLN(a,n)=1 là giả Fermat. Mặc dù các số Carmichael là rất hiếm, nhưng phép thử Fermat rất ít được dùng so với các phương pháp khác như kiểm tra Miller-Rabin hay kiểm tra Solovay-Strassen.

Nói chung, nếu n không là số Carmichael thì ít nhất một nửa các số

là bằng chứng Fermat. Để chứng minh điều này, giả sử a là một bằng chứng Fermat và a1, a2,..., as là giả Fermat. Khi đó

và do đó tất cả a × ai for i = 1, 2,..., s là bằng chứng Fermat.

Chú thích

[sửa | sửa mã nguồn]

Tham khảo

[sửa | sửa mã nguồn]
Chúng tôi bán
Bài viết liên quan
Nhân vật Izana Kurokawa trong Tokyo Revengers
Nhân vật Izana Kurokawa trong Tokyo Revengers
Izana là một người đàn ông mang nửa dòng máu Philippines, nửa Nhật Bản, có chiều cao trung bình với đôi mắt to màu tím, nước da nâu nhạt và mái tóc trắng ngắn thẳng được tạo kiểu rẽ ngôi giữa
Cẩm nang du lịch tự túc ở Lào
Cẩm nang du lịch tự túc ở Lào
Sau khi tự mày mò thông tin du lịch Lào và tự mình trải nghiệm, tôi nghĩ là mình nên có một bài viết tổng quát về quá trình chuẩn bị cũng như trải nghiệm của bản thân ở Lào
Mập và ốm: thể tạng cơ thể và chiến lược tập luyện phù hợp
Mập và ốm: thể tạng cơ thể và chiến lược tập luyện phù hợp
Bài viết này cung cấp góc nhìn tổng quát về ba loại thể tạng phổ biến nhằm giúp bạn hiểu rõ cơ thể và xây dựng lộ trình tập luyện, nghỉ ngơi và ăn uống phù hợp.
Download anime Plunderer Vietsub
Download anime Plunderer Vietsub
Alcia, một thế giới bị chi phối bởi những con số, mọi người dân sinh sống tại đây đều bị ép buộc phải “count” một thứ gì đó