Trong bài viết này sẽ mô tả hai cách để kiểm tra một số nguyên bất kì có phải là số nguyên tố hay không. Một thuật toán với số lượng bước và không gian tính toán là (order of growth Θ(
√n), cái còn lại là Θ(logn).
Tìm ước số
Từ thời xa xưa, toán học được xem là một chủ đề thú vị với những vấn đề liên quan đến số nguyên tố, và nhiều người đã nghiên cứu nhiều cách khác nhau để kiểm tra xem liệu rằng các số có phải là nguyên tố hay không?
Một cách để kiểm tả xem một số có phải là số nguyên tố hay không dựa vào tìm ước số của chính nó. Thủ tục sau tìm một số ước số nguyên nhỏ nhất (>1) của một số n cho trước. Bằng việc chia liên tục n với các số bắt đầu với 2.
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))
Bạn có thể kiểm tra một số có phải là số nguyên tố hay không như sau: n là số nguyên tố khi và chỉ
khi n là có ước số nhỏ nhất là chính nó.
(define (prime? n)
(= n (smallest-divisor n)))
Phần kiểm tra cuối cùng của find-divisor dựa trên sự thật rằng nếu n không phải là một số nguyên tố thì nó phải có một ước số nhỏ hơn hoặc bằng √n. Điều này có ý nghĩa là thuật toán chỉ cần kiểm tra các ước số giữa 1 và √n. Kết quả là số bước cần thiết để xác định mọt có có phải là số nguyên tố hay không sẽ có (order of growth Θ(√n)).
The Fermat test
order of growth Θ(logn) của việc kiểm tra tính nguyên tố cần dựa vào kêt quả từ lý thuyết một số được biết đến với tên gọi là Fermat’s Little Theorem.
Fermat’s Little Theorem: Nếu n là một số nguyên tố và a là một số nguyên dương bất kỳ nhỏ hơn n, thì từ a tăng đến ví trí số thứ n tương đương với a modulo n ( số dư n/a) .
Hai số được xem như là tương ứng với đồng vị n nếu cả hai có số cùng số dư khi bị chia bởi n. Số dư của một số khi bị chia bởi n cũng tương ứng với số dư của a modulo n, hoặc đơn giản như a modulo n)
Nếu n không phải là số nguyên tố thì nói chung hầu hết các số a < n sẽ không thỏa mãn mối quan hệ trên. Điều này dẫn đến thuật toán sau để kiểm tra tính nguyên tố: Cho một số n, chọn một số ngẫu nhiên a < n và tính số dư của a modulo n. Nếu số dư không bằng a, thì n chắc chắn không phải là số nguyên tố. Nếu là a, thì cơ hội để n là số nguyên tố sẽ nhiều hơn. Bây giờ chọn một số ngẫu nhiên khác và kiểm trả như trên. Nếu nó cũng thõa mãn điều kiện, thì chúng ta có nhiều điều kiện xác đáng hơn rằng n là một số nguyên tố.
Bằng việc chọn nhiều giá trị ngẫu nhiên ahown, và kiểm tra như trên, thì chúng ta có thể tự tin vào kết quả của mình hơn. Thuật toán ngẫu nhiên này được biết đến như là thuật toán Fermat.
Để thực thi thuật toán Fermat, chúng ta cần một procedure tính toán hàm lũy thừa của một số đồng vị dư với một số khác.
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder
(square (expmod base (/ exp 2) m))
m))
(else
(remainder
(* base (expmod base (- exp 1) m))
m))))
Tương tự với procedure fast-expt in bài lũy thừa một số. Thuật toán này cũng sử dụng bình phương liên tục, vì vậy số bước cũng sẽ là Θ(logn);
Thuật toán Fermet sử dụng cách chọn một số ngẫu nhiên a từ 1 đến n-1 và check xem liệu rằng số dư của n của số thứ n với a có bằng a hay không. Sử dụng procedure ramdam để chọn một số ngẫu nhiên a, chúng ta cho rằng procedure đó đã được thêm vào ngôn ngữ lập trình. Procedure random trả về một số nguyên dươn nhỏ hơn số n nhập vào. Từ đó, chúng ta sẽ đạt được một số ngẫu nhiên tăng dần đều +1.
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
Phương thức xác suất:
Thuật toán Fermat có đặc điểm khác với hầu hết các thuật toán, ở chỗ câu trả lời luôn đảm bảo đúng. Đây, trong Fermat kết quả đúng với xác suất không phải tuyệt đối. Chính xác hơn, nếu n fail trong phép kiểm tra Fermat thì chúng ta có thể chắc chắn rằng n không phải là số nguyên tố. Nhưng sự thật rằng n đã vượt qua bài kiểm tra, mặc dù là một dấu hiệu cực kỳ rõ ràng nhưng vẫn chưa đảm bảo rằng n là số nguyên tố. Điều chúng tôi muốn nói là đối với bất kỳ số n, nếu chúng ta thực hiện phép kiểm tra đủ số lần và thấy rằng n luôn luôn vượt qua bài kiểm tra thì xác suất xảy ra lỗi trong bài kiểm tra tính nguyên tố của chúng ta có thể chấp nhận với xác suất sai nhỏ nhất có thể.
Thật không may, khẳng định này không hoàn toàn chính xác. Có tồn tại những số đánh lừa được bài kiểm tra Fermat: những số n không phải là số nguyên tố nhưng vẫn có tính chất a^n đồng dư với modulo n với mọi số nguyên a < n. Những con số như vậy cực kỳ hiếm nên phép thử Fermat khá đáng tin cậy trong.
Có nhiều biến thể kiểm tra Fermat không thể bị đánh lừa. Trong các bài kiểm tra này, như với phương thức Fermat., một bài kiểm tra tính nguyên tố của một số nguyên n bằng việc lấy một số nguyên ngẫu nhiên a <n và check một vài điều kiện phụ thuộc của n và a. Ở khía cạnh khác, ngược với bài kiểm tra Fermat , một điều có thể chứng minh rằng, với bất kì n nào, điều kiện không đúng với hầu hết các số nguyên a < n trừ khi n là số nguyên tố.
Hơn nữa, nếu n vượt qua kiểm tra đối với các số random a, cơ hội để khẳng định sẽ tốt hơn n là một số nguyên tố. Nếu n pass kiểm tra cho việc chọn hai số random a, cơ hội để khẳng định cũng sẽ tốt hơn 3, 4 lần rằng n là số nguyên tố. Bằng việc chạy nhiều lần test, thì xác suất khẳng định sai sẽ ít lại.
Sự tồn tại của các thử nghiệm mà người ta có thể chứng minh rằng khả năng xảy ra lỗi trở nên cực nhỏ tùy ý đã làm dấy lên sự quan tâm đến các thuật toán tính xác suất thuộc dạng này, chúng được gọi là thuật toán xác suất. Cũng có rất nhiều hoạt động nghiên cứu trong lĩnh vực này, và các thuật toán xác suất đã được áp dụng hiệu quả rộng rãi cho nhiều lĩnh vực.
Bài viết tiếp theo: Công thức hóa các abstraction với các thủ tục bậc cao
