使用 6k+/-1 规则改进试验划分素数测试

Question

我正在学习试用除法素性测试的基础知识，因此，在代码中实现它。使用许多技巧可以提高算法的性能，例如：

1) 运行试验除法只到平方根(n)

2) 通过创建一个高达平方根 (n) 的筛子来用内存换取时间，然后运行仅在创建的筛子

中的素数上进行试验划分

但是如果发现 n%6 (n mod 6) 的值是 1 or 5 （使用 6k +/- 1 条规则）。在我们的素数确定测试中使用这个规则不会提高它的性能吗？如果是，为什么没有在任何地方提到它？如果不是，为什么会这样？

谢谢。

Answer 1

看来您属于高于初学者水平（永远不会想出这个想法的人）和低于寻求极致性能的人的类别。所以这个想法对初学者来说有点难以解释，而对非常高级的人来说似乎微不足道。

它将运行时间减少三分之一，或者让您同时测试 50% 以上的数字。如果除数不是太大，您可以通过减少测试来节省更多：假设您测试了一个大约十亿的数字。你有一个循环，除数 d = 6k-1，你想测试 d 和 d+2 = 6k+1。所以你只测试 d^2 ≤ p，你不测试 (d+2)^2 ≤ p。最坏的情况是，您多测试了一个除数。最好的情况是，您保存几千个 (d+2)^2 ≤ p 的测试。

通过观察唯一可能的 ≥ 30 素数是 30k + 1、7、11、13、17、19、23、29，避免 30k + 5 和 30k + 25，您可以节省更多。

Answer 2

您测试 n % 6 的想法完全等同于测试 n % 2 和 n % 3 —— 因此，如果您将后者作为普通试验部门的一部分进行，那么进行前者就是多余的。

的一个密切相关的想法是（在考虑 2 和 3 之后）仅查看形式为 6k+1、[=14= 的试验除数]，正如@gnasher729 在他们出色的回答中解释的那样。

Answer 3

这个技巧的工作原理：生成一堆小素数的 M 的乘积。然后，当测试一个数 N 时，如果 (N%M) 为 0 或与 M 有一个公因数，则可以立即说 N 是合数。

您使用了 6，即 2 和 3 的乘积。在可能的模数 0、1、2、3、4、5 中，只有 1 和 5 没有因数 2 或 3。

尽管 6 并没有什么特别之处——您可以对任何模数执行相同的操作，尽管您想让它成为小素数的乘积以最大化复合模数的密度。

请注意，在进行此检查后（如 gnasher 所示），您只需要测试与 M 没有共同因子的试验除数。

Answer 4

这里的通用方法叫做Wheel Factorization。最简单的轮子是特殊对待 2，然后只测试奇数：2 轮。下一个最简单的是您在问题中提到的 2,3 轮。 @gnasher729 给出了上面 2、3、5 轮的数字。

您可以通过从 5 开始交替添加 2 和 4 来生成 2,3 轮的数字。

伪代码：

boolean isPrime(num)

  // Deal with factor 2.
  if (num MOD 2 = 0) then
    return (num = 2)
  endif

  // Deal with factor 3.      
  if (num MOD 3 = 0) then
    return (num = 3)
  endif

  // Factors >= 5.
  limit <-- 1 + sqrt(num)
  trialFactor <-- 5
  step <-- 2
  while (trialFactor < limit) do
    if (num MOD trialFactor = 0)
      // Number not prime
      return false
    endif
    trialFactor <-- trialFactor + step
    step <-- 6 - step
  endwhile

  // Number is prime here.
  return true

end

这比 Sieve 使用更少的内存，但对于非常大的素数来说太慢了。

使用 6k+/-1 规则改进试验划分素数测试

Improving trial division primality test using 6k+/-1 rule

algorithm

primes

primality-test