14
Làm cách nào để nhanh chóng tạo số nguyên tố ngẫu nhiên, có nghĩa là dài 1024 bit?Số nguyên ngẫu nhiên
A
Trả lời
24
Tạo 1024 bit ngẫu nhiên. Sử dụng một nguồn ngẫu nhiên đủ mạnh cho mục đích của bạn.
Đặt bit cao nhất và thấp nhất thành 1. Điều này đảm bảo không có số 0 đứng đầu (ứng cử viên chính đủ lớn) và không phải là số chẵn (chắc chắn không phải số nguyên tố).
Test for primality. Nếu đó không phải là số nguyên tố, hãy quay lại 1.
Hoặc, sử dụng chức năng thư viện để tạo số nguyên tố cho bạn.
+5
Tùy chọn - đọc lên phân phối số nguyên tố để đảm bảo rằng thuật toán này khả thi (tức là sẽ không cần hàng nghìn tỷ lần thử). –
+3
Nó sẽ không cần hàng tỷ tỷ lần thử: mật độ của số nguyên tố là rất xấp xỉ 1 trong ln (x). Trong trường hợp này là 1 trong 710, nhưng vì anh ta tránh được số chẵn 1 ở 305. Nó sẽ cần hàng nghìn tỷ đơn vị thử nghiệm để chứng minh nó chính, trừ khi bạn sử dụng một thử nghiệm nguyên thủy không tầm thường. Và nếu bạn sẽ cần một thử nghiệm nguyên thủy không tầm thường, thì không rõ ràng với tôi tại sao bạn cũng sẽ không sử dụng một phương tiện không tầm thường để tạo ra các ứng cử viên tốt hơn. –
+0
Cảm ơn, đây là một ý tưởng ban đầu. Mặc dù tôi muốn biết nếu có một giải pháp nhanh hơn. – gmile
22
Sử dụng chức năng thư viện, chẳng hạn như OpenSSL. Không cần phải tự mình viết.
0
Để kinh doanh bộ nhớ cho tốc độ bạn chỉ có thể tạo ra chúng và lưu trữ chúng trong một danh sách và sau đó chọn ngẫu nhiên một.
Chỉnh sửa: Tự nhiên bạn không thể tạo ra tất cả những gì tốt nhất bạn có thể đạt được là giả ngẫu nhiên với chi phí bộ nhớ cao. Ngoài ra điều này là không tốt nếu bạn muốn nó cho an ninh.
+1
"tạo chúng"? Tất cả bọn họ!?! –
+2
Điều này sẽ không tốt nếu các số nguyên tố là cần thiết vì lý do bảo mật, như thường lệ. –
+0
Đánh dấu: Ngoài vấn đề hiển nhiên thực sự lưu trữ tất cả các số nguyên tố 1024 chữ số, đó là vấn đề với điều đó? Bạn sẽ chọn một thủ công ngẫu nhiên. – Joey
3
1024 là rất nhiều. Bạn có chắc chắn một nguyên tố xác suất sẽ không làm gì? Trình tạo thủ tố xác suất là một phần của JDK
+3
-1, tôi nghĩ rằng bạn đang đề xuất một máy phát điện nguyên tố xác suất khi bạn nói giả nguyên tố. Thủ tố giả không phải là số nguyên tố (nghĩa là nó có số chia nhỏ hơn 1 và chính nó) mặc dù nó có một số thuộc tính chung với số nguyên tố, và phần tử giả không thay thế cho số nguyên tố, đặc biệt đối với mật mã. Thực tế là các số nguyên tố giả mà vượt qua các thử nghiệm xác suất là rất hiếm, làm cho các phép thử như vậy tốt cho các số lớn được tạo ngẫu nhiên. Nhưng nói rằng các OPs cần có thể thỏa mãn bởi một giả giả rõ ràng là sai. Java có một kiểm tra chính xác xác suất/máy phát điện, đó là khả năng những gì bạn có nghĩa là. – MAK
+1
Vâng, đây là ý tôi là – glebm
+1
@Glex: Sau đó, vui lòng chỉnh sửa câu trả lời của bạn để nó không gây hiểu lầm. – MAK
0
Trong PARI/GP:
randomprime([2^1023,2^1024])
Nếu bạn muốn làm điều này trong 'chế độ thư viện'
#include <pari/pari.h>
// ...
randomprime(mkvec2(int2u(1023), int2u(1024)))
1
Bạn không chỉ định một bối cảnh/ngôn ngữ/nền tảng .. Nếu bạn muốn muốn sử dụng hệ vỏ và hệ thống giống như Unix/Unix, bạn có thể xem xét giải pháp liên quan đến phiên bản OpenSSL> = 1.0.0:
$ openssl prime -generate -bits 1024
140750877582727333214379261853877378646889234118675380673028200387281415297520423589261211081966230040412916644372766351028035798201654335110081318739796178745233127842988596480299276295476504358587725867882394416543075082108266054273016211760684113070285409887820598314292803190900634009988950624354964653677
Nếu bạn nhận được kết quả tương tự, điều gì đó rất sai với vũ trụ.
Thêm -hex tùy chọn nếu bạn thích hệ thập lục phân.
Các vấn đề liên quan
- 1. tạo ngẫu nhiên số nguyên 64 bit
- 2. số ngẫu nhiên không quá ngẫu nhiên
- 3. Số nguyên ngẫu nhiên Javascript giữa hai số
- 4. Trình tạo số ngẫu nhiên tạo số nguyên cho Java
- 5. Số ngẫu nhiên hoặc số dương Javascript ngẫu nhiên
- 6. Nhận số nguyên ngẫu nhiên trong phạm vi (x, y]
- 7. tạo các số nguyên ngẫu nhiên với xác suất
- 8. Số ngẫu nhiên Javascript?
- 9. Trình tạo số ngẫu nhiên phân phối ngẫu nhiên
- 10. số C# ngẫu nhiên không là "ngẫu nhiên"
- 11. đặc biệt ngẫu nhiên số
- 12. Số ngẫu nhiên với jQuery?
- 13. Số ngẫu nhiên xác suất
- 14. Tạo số ngẫu nhiên lớn
- 15. Số ngẫu nhiên trong C
- 16. Phân tích số ngẫu nhiên
- 17. Tạo số ngẫu nhiên CUDA
- 18. C++ 11 số ngẫu nhiên
- 19. Số int64 và float64 ngẫu nhiên
- 20. Java Tạo số ngẫu nhiên {-1,0,1}
- 21. tạo số ngẫu nhiên ngắn trong java?
- 22. Số ngẫu nhiên giữa 2 số đôi
- 23. Tại sao không ngẫu nhiên() ngẫu nhiên?
- 24. Số ngẫu nhiên trong POSIX C API
- 25. Tìm xác suất của hai số nguyên được chọn ngẫu nhiên (từ n số nguyên) tương đối nguyên tố
- 26. Tạo số ngẫu nhiên có trọng số trong R
- 27. Cách tạo 5 số ngẫu nhiên với tổng số 100
- 28. Thuật toán để tạo số ngẫu nhiên
- 29. Phân phối số ngẫu nhiên thế hệ
- 30. Cách tạo số ngẫu nhiên lớn C
Bạn đang sử dụng ngôn ngữ nào? –
Bạn có nghĩa là hoàn toàn chắc chắn nguyên tố, hoặc có khả năng nhất cho tất cả các mục đích thực tế? Những số nguyên tố này sẽ được sử dụng cho mục đích bảo mật hay cái gì khác? –
@Mark_Byers Tôi đang sử dụng Ruby. Vâng, đây là mục đích an ninh. Tôi đang cố gắng tạo mã hóa RSA. – gmile