如何测试1000位长的素数?

如果足以确定一个数字是否可能是素数,则可以使用内置的 isProbablePrime

• 如果调用返回true,则该数字为素数的概率超过(1-1/(2^确定性))。
• 如果呼叫返回false,则该号码肯定不是素数。

Lucas pseudoprime test 和 Rabin-Miller strong pseudoprime test 在基数2和基数3中。如果这三个结果都是 可能是最好的 然后,出于所有实际的原因,你应该这样认为。这个测试没有已知的反例。如果必须生成素性证书,则可以使用 elliptic curve primality prover ,但速度会慢得多。

你应该使用 BigInteger

知道它的形式是6k+/-1告诉你它是否“安全”——即 Q+1和Q-1都有较大的因子,使得Q更难被因子化(因此对于加密目的来说是“安全的”)。但表格6k+/-1中的大多数数字都是复合的。

"Safe Prime" page from Wikipedia

如果您想编写自己的例程来测试1000位数字的素性,那么您应该像其他答案所建议的那样使用BigInteger类。你可以用费马 首先测试,它会告诉你这个数字是“绝对复合”还是“可能是素数”。 然后,您可以使用计算更密集的测试,如Miller Rabin或Solovay Strassen 关于最终确定测试的“可能素数”。

Primality testing algorithms from Wikipedia

一个1000位数字使用少于350字节的BigDecimal内存。你会发现你可以处理比这个大得多的数字。

很多 大约10^31,这将需要很长时间,大约10^18年。

如果你不喜欢概率方法,有一个 deterministic polynomial algorithm

但是,除非一位神在玩弄赔率,拉你的腿或其他什么,否则你可能应该只使用概率方法,这会更快。

你可以利用一些想法。

• 检查除数是否小于sqrt(素数)
• 检查仅除以素数

结合这些方法,您可以大大加快验证速度。

此链接可以帮助您: http://www.osix.net/modules/article/?id=791

当然要使用biginger。

wolframalpha

f、 x: “175417963415175253817696597433408585811164204614256364837827967是素数吗?”

返回: “175417963415175253817696597433408585811164204614256364837827967是素数!”

我想你可以用BigInteger来表示非常大的数字。

但是,有一点您应该注意,格式为6k+1的所有数字都是素数。例如

when k=341,
6k +1 = 6(341) +1 = 2046 + 1= 2047

Now 2047 can be divided by 23 like so

2047/23 = 89 

因此,在生成素数时使用它可能不是很好