2

我已经搜索了确定数字是否为素数的方法，但大多数方法要么是概率的（米勒拉宾），要么是小于 64 位的数字。

另一种解决方案是使用带有一些改进或筛子的蛮力方法，但是当数字超过 64 位阈值时，这两种方法都不是很有效。

4

2 回答 2

4

你要找的东西不存在。没有简单的确定性素性检验始终适用于所有整数范围。

您已经了解 Miller-Rabin 检验。它可以在特定范围内确定；有关详细信息，请参见此处或此处。如果您假设黎曼假设，那么对于所有整数a且 1 < a < 2(log n )² ，如果n是a -SPRP（米勒强伪素数），则n是素数。Baillie-Wagstaff 测试是一个类似但更好的测试。它不是确定性的，但没有已知的失败。

对于n到 2 128的数字，分解n - 1 并使用 Pocklington 检验来证明素数并不难。您可以使用试除法、Pollard rho 或 ECM 来执行分解。还有一些测试 ( BLS75 ) 可以基于部分分解来证明素数。较大的n也可以使用 Pocklington 检验证明是素数，尽管有时分解变得困难。

对于高达约 10 1000的n，快速 ECPP 素数测试并非不合理，但对于该范围内的较大数字，可能需要一段时间。除此之外，除非您的号码有某种特殊形式，否则您几乎不走运。

于 2020-02-06T16:53:39.887 回答
3

我会假设你想要的是一个可证明的正确答案，而不是完全避免随机性。

  1. 运行几轮 Miller-Rabin 素数测试。如果这失败了，你知道这个数字是复合的，你就完成了。
  2. 因式分解 n-1。为此，最简单的是 Pollard 的 rho 算法。如果这还不够快，请使用二次筛。
  3. 使用相同的递归方法检查因子是否为素数。如果它们是复合的，请继续分解它们。
  4. 使用 Lucas Primality Test：尝试找到 n-1 阶的乘法群模 n 的生成器。选择一个随机数 a，检查 a^(n-1) = 1 (mod n)，并且对于 n-1 的所有质因数 p，a^((n-1)/p) ≠ 1 (mod n) . 如果这是真的，a 是一个生成器，并且 n 可以证明是一个素数，那么你就完成了。
  5. 如果 n 是素数，则找到生成器的成功概率为 (1-1/p 1 )(1-1/p 2 )... 其中 p 1 , p 2 , ... 是 n 的不同素因数-1。这至少是 1 / O(log log n)。因此，在 O(log log n) 尝试之后，您应该成功证明 n 是素数。
  6. 如果你一直无法证明 n 是素数，请返回步骤 1。也许它毕竟是复合的。
于 2020-02-06T17:19:20.223 回答