Tài liệu tham khảo về lý thuyết mật mã, cách làm và giải mật mã an toàn. | 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ế phuơ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 nhu thuật toán Miller- Rabin hoặc là thuật toán Solovay- Strasen . Cả hai thuật toán trên đều đ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 đuợ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ố duới một mức nguỡ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 thuơc xác định cho tới khi tìm đuợc một số nguyên tố. Một kết quả nỗi tiếng trong lý thuyết số đuợ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 đuợ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 cu 177 số nguyên ngẫu nhiên p với kích thuớc tuơ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 đuợc các nguyên tố đủ lớn và do đó về mặt thực thể ta có thể thiết lập đuợc một hê mật RSA. Sau đây sẽ tiếp tục xem xét điều này đuợc thực hiên nhu 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 đuợ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 nguợc lại thuật toán không sử dụng các số ngẫu nhiên sẽ đuợc gọi là một thuật toán tất định . Các định nghĩa sau .
