tailieunhanh - Cách kiểm tra tính nguyên tố xác suất

Kiểm tra tính nguyên tố xác suất Để thiết lập hệ mật RSA, ta phải tạo ra các số nguyên tố ngẫu nhiên lớn (chẳng hạn có 80 chữ số). | Vietebooks Nguyễn Hoàng Cương CHƯƠNG 4 KIỂM TRA TÍNH NGUyÊN Tố XÁC SUẤT Để thiết lập hệ mật RSA ta phải tạo ra các số nguyên tố ngẫu nhiên lớn chẳng hạn có 80 chữ số . Trong thực tế phương cách thực hiện điều này là trước hết phải tạo ra các số ngẩu nhiên lớn sau đó kiểm tra tính nguyên thuỷ của chúng bằng cách dùng thuật toán xác suất Monte- Carlo thời gian đa thức chẳng hạn như thuật toán Miller- Rabin hoặc là thuật toán Solovay- Strasen . Cả hai thuật toán trên đều được trình bày trong phần này. Chúng là các thuật toán nhanh tức là một số nguyên n được kiểm tra trong thời đa thức theo log2n là số các bít trong biểu diện nhị phân của n . Tuy nhiên vẫn có khả năng là thuận toán cho rằng n là số nguyên tố trong khi thực tế n là hợp lệ số. Bởi vậy bằng cách thay đổi thuật toán nhiều lần có thể giảm xác suất sai số dưới một mức ngưỡng cho phép sau này sẽ thảo luận kỹ hơn một chút về vấn đề này . Một vấn đề quan trọng khác là cần phải kiểm tra bao nhiêu số nguyên ngẫu nhiên với kích thươc xác định cho tới khi tìm được một số nguyên tố. Một kết quả nỗi tiếng trong lý thuyết số được gọi là định lý số nguyên tố phát biểu rằng số các số nguyên tố không lớn hơn N xấp xỉ bằng N ln N. Bởi vậy nếu p được chọn ngẫu nhiên thì xác suất p là một số nguyên tố sẽ vào khoảng 1 ln p. Với một mođun 512 bít ta có 1 ln p 1 77. Điều này có nghĩa là tính trung bình cư 177 số nguyên ngẫu nhiên p với kích thước tương ứng sẽ có một số là số nguyên tố. Dĩ nhiên nếu chĩ hạn chế xét các số nguyên lẻ thì xác suất sẽ tăng gấp đôi tới khoảng 2 177 . Bỡi vậy trên thực tế hoàn toàn có khả năng tạo được các nguyên tố đủ lớn và do đó về mặt thực thể ta có thể thiết lập được một hệ mật RSA. Sau đây sẽ tiếp tục xem xét điều này được thực hiên như thế nào. Một bài toán quyết định là một bài toán toán trong đó một câu hỏi cần được trả lời có hoặc không . Một thuật toán xác suất là một thuật toán bất kỳ có sử dụng các số ngẫu nhiên ngược lại thuật toán không sử dụng các số ngẫu nhiên sẽ được gọi là một .