16

如何快速生成一个随机素数，肯定是 1024 位长？

4

6 回答 6

25

  1. 生成 1024 个随机位。使用足够强大的随机源来满足您的预期目的。

  2. 将最高位和最低位设置为 1。这确保没有前导零（素数候选者足够大）并且它不是偶数（绝对不是素数）。

  3. 测试素数。如果不是素数，则返回 1。

或者，使用为您生成素数的库函数。

于 2009-11-20T10:52:32.060 回答
22

使用库函数，例如 OpenSSL。这个没必要自己写。

示例：http ://ardoino.com/7-maths-openssl-primes-random/

上面的链接不起作用，因此您可以使用此存档链接。

于 2009-11-20T10:47:28.157 回答
3

1024很多。你确定概率素数不会吗？概率素数生成器是 JDK 的一部分

于 2009-11-20T10:50:35.233 回答
2

您没有指定上下文/语言/平台.. 如果您想使用类似 unix/linux 的系统和 shell，您可以考虑涉及 OpenSSL 版本 >= 1.0.0 的解决方案：

$ openssl prime -generate -bits 1024
140750877582727333214379261853877378646889234118675380673028200387281415297520423589261211081966230040412916644372766351028035798201654335110081318739796178745233127842988596480299276295476504358587725867882394416543075082108266054273016211760684113070285409887820598314292803190900634009988950624354964653677

如果你得到同样的结果，那么宇宙就有很大的问题。

-hex如果您喜欢十六进制系统，请添加选项。

于 2015-08-15T07:53:42.270 回答
0

为了用内存换取速度，你可以生成它们并将它们存储在一个列表中，然后随机选择一个。

编辑：当然你不能全部生成它们，所以你能达到的最好的就是伪随机性，内存成本很高。如果你想要它的安全性，这也不好。

于 2009-11-20T10:48:05.563 回答
0

在PARI/GP中：

randomprime([2^1023,2^1024])

如果您想在“图书馆模式”下执行此操作

#include <pari/pari.h>
// ...
randomprime(mkvec2(int2u(1023), int2u(1024)))
于 2015-07-09T18:01:40.360 回答