Tôi đang chơi xung quanh và cố gắng viết một bản thực thi RSA. Vấn đề là tôi đang mắc kẹt khi tạo ra các số nguyên tố khổng lồ có liên quan đến việc tạo ra một cặp khóa. Ai đó có thể chỉ cho tôi một cách nhanh chóng để tạo ra số nguyên tố khổng lồ/số nguyên tố có thể xảy ra?Tạo các số nguyên tố lớn thực sự
Bạn không tạo chính xác số nguyên tố. Bạn tạo một số lẻ lớn ngẫu nhiên, sau đó kiểm tra nếu số đó là số nguyên tố, nếu không tạo số ngẫu nhiên khác. Có một số luật về số nguyên tố cơ bản cho biết tỷ lệ cược của bạn là "đánh" một số nguyên tố thông qua các lần thử ngẫu nhiên là (2/ln n)
Ví dụ, nếu bạn muốn số nguyên ngẫu nhiên 512 bit, bạn sẽ tìm thấy một trong 2/(512 * ln (2)) Vì vậy, khoảng 1 trong mỗi 177 số bạn thử sẽ là số nguyên tố.
Có nhiều cách để kiểm tra xem một số có phải là số nguyên tố hay không, một cách tốt nhất là "kiểm tra Miller-Rabin" như đã nêu ở trên.
Ngoài ra, OpenSSL có một tiện ích để kiểm tra số nguyên tố:
$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime
Hãy xem cách TrueCrypt thực hiện việc đó. Ngoài ra, hãy xem Rabin-Miller để kiểm tra giả mạo lớn.
Tại sao bạn cho rằng TrueCrypt tạo số nguyên tố? Theo như tôi biết, nó chỉ sử dụng mật mã đối xứng. – CodesInChaos
Bạn không đề cập đến ngôn ngữ bạn đang sử dụng. Một số có một phương pháp làm điều này được xây dựng trong. Ví dụ, trong java này là dễ dàng như gọi nextProbablePrime() trên một BigInteger.
Tôi đang sử dụng Objective-C – computergeek6
Tùy thuộc vào cách chức năng đó được triển khai, bạn có thể thỏa hiệp lựa chọn chính của mình nếu không gian tìm kiếm bị giảm. – Stephen
Câu trả lời trước đó là không chính xác: 2 * 3 * 5 * 7 * 11 * 13 + 1 = 30031 = 509 * 59.
Tôi nghĩ rằng các poster được misremembering sự (thực) chứng minh rằng có là một số lượng số nguyên tố không đếm được.
Trên thực tế, chỉ có số lượng số nguyên tố có thể đếm được (nhưng vô hạn). Ngoài ra, các poster khác (có bài viết dường như bị xóa bây giờ) không phải là misremembering xây dựng từ các bằng chứng (đó là thực sự làm thế nào nó đi) nhưng thay vì lạm dụng nó. – oggy
Thật vậy. Hãy nhớ rằng các số nguyên có thể đếm được, số nguyên sẽ là "1, 2, ...". Vì vậy, là số nguyên tố và lý trí; đó là số thực không thể đếm được. – jrockway
Mono có lớp BigInteger là nguồn mở như java. Bạn có thể nhìn vào chúng. Chúng có lẽ là di động :) g'luck
Có một thuật toán do U. Maurer mà tạo ra ngẫu nhiên chứng minh (trái ngược với thống kê cao có thể xảy ra) số nguyên tố mà hầu như thống nhất phân phối trên tập hợp tất cả các số nguyên tố có kích thước đặc biệt. Tôi có triển khai Python của nó khá hiệu quả tại: http://s13.zetaboards.com/Crypto/topic/7234475/1/
Cảm ơn. Điều này giải thích rất nhiều vấn đề tôi gặp phải. – computergeek6
bạn cũng có thể tạo số nguyên tố trong openssl: 'openssl prime -generate -bits 512' – mykhal