如何测试1000位数的素数？

Question

我试图找出数字是否是1000或更长的素数.我想使用的算法是6k +/- 1

我面临的问题是如何在java中存储这么长的数字,它是以字符串作为输入.

要么

为了做到可分性,应该只考虑数字的最后几位数.

请指教

Answer 1

如果足以确定一个数字是否为PROBABLY prime,则可以使用内置的isProbablePrime函数

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

Answer 2

你应该在2号和3号基地使用Lucas pseudoprime测试和Rabin-Miller强伪测试.如果所有三个都给出了可能是素数的结果,那么出于所有实际原因你应该考虑它.此测试没有已知的反例.如果你必须生成素数证书,那么你可以使用椭圆曲线素数证明器,但它会非常慢.

Answer 3

如果需要在32/64位空间之外处理整数,则应使用BigInteger.不知道你需要担心的是否存在实际限制.