Top Ad unit 728 × 90

Latest news

recent

Kiểm tra số nguyên tố (Primality test) - lời giải đầu tiên

Kiểm tra một số có phải số nguyên tố hay không là một bài toán khá quan trọng trong khoa học máy tính. Vì số nguyên tố được sử dụng rất rộng rãi trong các giải thuật mã hóa dùng khóa mở ( public key cryptography algorithms). Ngoài ra nó còn được ứng dụng trong các bộ phát sinh số giả ngẫu nhiên (pseudorandom) và bảng hash (hash table). Người ta phân loại các thuật toán kiểm tra một số là số nguyên tố hay không thành 2 nhóm: nhóm thuật giải tất định (deterministic) và nhóm thuật giải dựa trên xác suất (probabilistic). Để dễ dàng trong việc tiếp cận vấn đề ở mức cao hơn trong hàng tá các thuật toán phức tạp ở những bài viết sau, trong thảo luận này tôi sẽ giới thiệu khái niệm và sẽ đi sâu vào chi tiết một giải thuật sơ khai nhất có tên là giải thuật chia thử (trial division) và từng bước tối ưu của nó.
  1. Số nguyên tố là gì?
    Số nguyên tố là một số mà chỉ chia hết cho hai số tự nhiên khác nhau là 1 và chính nó. Hướng đi sơ khai nhất để kiểm tra một số có phải là số nguyên tố hay không là bám sát theo định nghĩa của nó. Chỉ cần chia thử lần lượt  số đó cho các số tự nhiên trong khoảng  từ 1 tới nó, nếu có tồn tại số mà nó chia hết thì đó là số không nguyên tố  (composite) và ngược lại. Sau đây là thuật toán kiểm tra nguyên tố với số tự nhiên n:

        * Nếu n1, trả ra kết quả không phải nguyên tố;
        * Mặt khác, với tất cả các số nguyên m có giá trị từ 2 đến n - 1, kiểm tra nếu n chia hết cho m thì n không nguyên tố;
        * Nếu không có ước số nào được tìm thấy, kết luận n là số nguyên tố.

    Chú ý: 1 không là số nguyên tố vì không thỏa tính khác nhau trong định nghĩa.

  2. Tối ưu thuật toán lần 1
    Như các bạn thấy thuật toán chia thử (trial division) ở trên khá đơn giản, tuy nhiên cũng dễ nhận ra là thuật toán này đi theo hướng vét cạn do đó hoàn toàn không tối ưu. Một hướng nâng cấp mà ta nên nghĩ tới đó là làm sao để giãm phạm vi thử chia xuống. Thật may mắn  khi chúng ta có thể chứng minh rằng thay vì chia thử cho toàn bộ các số từ 2 đến (n-1) chúng ta chỉ cần kiểm tra các ước số nhỏ hơn hay bằng căn bậc hai của n dựa vào quy tắc sau:
    Nếu n có một ước số d (1 < d < n), thì nó cũng có một ước số d0 (1 < d0 < √n).
    Nếu n được chia một cách hoàn toàn bởi căn bậc hai, khi đó nó là một căn bậc hai hoàn hảo và  hẳn nhiên n không nguyên tố. Mặt khác, giả sử rằng ước số đầu tiên được tìm thấy là d1√n < d1 < n., khi đó n  được chia một cách hoàn toàn bỡi d2 = n / d1, trong trường hợp này d2 phải nhỏ hơn √n. Vì vậy giả sử sai cho nên nếu tồn tại một ước số lớn hơn √n, thì sẽ có một ước số khác tạo thành cặp với nó nhỏ hơn √n.  Như vậy quy tắc trên đã được chứng minh.

  3. Tối ưu thuật toán lần 2
    Với bước tối ưu ở trên ta sẽ thu được sự tăng tốc đáng kể tuy nhiên vẫn còn một kẻ hở nữa có thể tận dụng để cải thiệm thêm xử lý. Giả sử n là số lẻ (odd) (số không chia hết cho 2), khi đó nó cũng sẽ không chia hết cho bất kì một số chẳn nào khác. Thuật toán sau khi áp dụng hai lần tối ưu sẽ như sau:

        * Nếu n1, trả ra kết quả không phải là nguyên tố;
        * Nếu n2, trả ra kết quả là số nguyên tố;
        * Nếu n là số chẳn, trả ra kết qua không phải là số nguyên tố;
        * Mặt khác, xét tất cả các số lẽ m từ 3 đến √n, nếu n chia hết cho m thì nó không nguyên tố;
        * Nếu không có ước số nào được tìm thấy, kết luậ n là số nguyên tố.

    Tổng quát hóa của ý tưởng này là khi thuật toán chỉ tiến hành kiểm tra các ước số nguyên tố.
  4. Độ phức tạp của thuật toán
    Giả sử rằng tính chia hết của hai số chỉ là một đơn vị phép tính (Điều này không đúng trong trường hợp số lớn), Độ phức tạp của thuật toán là O(√n). Lần tối ưu sau cùng cũng chỉ thay đổi  hằng số.  Khi quá trình kiểm tra chỉ tiến hành trên ước số nguyên tố (prime divisors) thì độ phức tạp của thuật toán trở thành O(√n / ln(n)).
    Ứng dụng chính của số nguyên tố là trong lĩnh vực mã hóa (cryptography), trong đó chúng ta cần tạo ra những số nguyên tố với hàng trăm chử số. Có vẻ như thuật toán được đề cập sẽ không  kiểm tra những số trong khoảng 10100 với thời gian thích hợp. Dù cho đó chỉ là  sự ứng dụng trong thực hành để  thực hiện công tác kiểm tra trước (pre-check). Một số khổng lồ đang được kiểm nghiệm nguyên tố  trước tiên sẽ kiểm tra khả năng chia được bởi cả triệu số nguyên tố đầu tiên. Nếu không có ước số nào được tìm thấy thì thuật toán dựa vào xác xuất sẽ được sử dụng.

  5. 100 số nguyên tố đầu tiên

  6. Mã nguồn C++



Binh Nguyen - Bioz
Kiểm tra số nguyên tố (Primality test) - lời giải đầu tiên Reviewed by Bioz on 3:35:00 PM Rating: 5
All Rights Reserved by IEEV © 2009 - 2016
Powered By Blogger, Designed by Sweetheme

Contact Form

Name

Email *

Message *

Powered by Blogger.