2

我需要最快的程序来检查 14 位（或更大）数字的素数。我在多个站点上进行了搜索，但我不确定我找到的站点是否可以处理这么大的数字。

4

4 回答 4

6

就主要测试而言，14 位数字并不是很大。当数字具有某种特殊结构时，可能会提供更快的专用测试（例如，如果它是梅森数），但一般来说，该范围内数字的最快测试是

  1. 按一些小数开始试除。如果您计划进行多次检查，则值得列出n最小的素数，以便试除法仅除以素数，对于单个测试，避免偶数测试除数（除了 2）和 3 的倍数（除了3），足够好。“小”的含义取决于解释，在 100 和 10000 之间选择截止似乎是合理的，许多（很少）除法仍然很快完成，并且他们找到了绝大多数的合数。

  2. 如果试验部门尚未确定复合数（或素数，如果它实际上小于截止值的平方），您可以使用已知对您感兴趣的范围具有确定性的快速概率素数测试之一在，通常的候选人是

    • Baillie/Pomerance/Selfridge/Wagstaff 检验，对基数 2 的强费马检验，然后是平方检验和（强）卢卡斯检验。这没有低于 2 64的误报，因此对于 14-18 位数字是确定的。
    • 对已知对所考虑范围具有确定性的一组碱基进行强费马检验。根据Chris Caldwell 的素数页，“如果n < 341,550,071,728,321是 2、3、5、7、11、13 和 17-SPRP，则 n 是素数”。

速度较慢且实施起来相当困难的是快速确定性通用素数测试、APR-CL、ECPP、AKS。他们应该已经在 14 位或更多位数的数字上击败了纯试除法，但比偶然已知的范围概率测试要慢得多。

但是，根据您的用例，最好的方法也可能是筛选一个连续范围的数字（例如，如果您想找到 10 14 -10 9和 10 14之间的素数，筛子会比数亿次快速个体素数测试）。

于 2013-06-05T10:11:07.433 回答
5

正如 Daniel Fischer 所指出的，14 位数字对于素性测试来说并不是特别大。这给了你几个选择。首先是简单的试划分：

function isPrime(n)
    d := 2
    while d * d <= n
        if n % d == 0
            return Composite
        d := d + 1
    return Prime

10^14 的平方根是 10^7，所以这可能需要一点时间。更快的是使用主轮：

struct wheel(delta[0 .. len-1], len, cycle)

w := wheel([1,2,2,4,2,4,2,4,6,2,6], 11, 3)

function isPrime(n, w)
    d := 2; next := 0
    while d * d <= n
        if n % d == 0
            return Composite
        else
            d := d + w.delta[next]
            next := next + 1
            if next == w.len
                next := w.cycle
    return Prime

这应该将幼稚的试用部门加快 2 或 3 倍，这可能足以满足您的需求。

更好的选择可能是 Miller-Rabin 伪素性测试仪。从一个强伪素测试开始：

function isStrongPseudoprime(n, a)
    d := n - 1; s := 0
    while d is even
        d := d / 2; s := s + 1
    t := powerMod(a, d, n)
    if t == 1 return ProbablyPrime
    while s > 0
        if t == n - 1
            return ProbablyPrime
        t := (t * t) % n
        s := s - 1
    return DefinitelyComposite

函数返回的每个a都是n素数ProbablyPrime的见证：

function isPrime(n)
    for a in [2,3,5,7,11,13,17]
        if isStrongPseudoprime(n, a) == DefinitelyComposite
            return DefinitelyComposite
    return ProbablyPrime

正如 Fischer 所指出的，根据Gerhard Jaeschke的一篇论文，对于n < 10^14，这是完全可靠的；如果要测试较大数字的素性，请随机选择 25 个见证人a 。该函数返回b ^ e (mod m )。如果您的语言不提供该功能，您可以像这样有效地计算它：powerMod(b,e,m)

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e % 2 == 1
            x := (b * x) % m
        b := (b * b) % m
        e := floor(e / 2)
    return x

如果你对这个测试背后的数学感兴趣，我谦虚地推荐我博客上的用质数编程的文章。

于 2013-06-05T13:47:47.347 回答
0

循环变量“x”以 1 递增，直到达到数字“num”的值。循环时使用模数检查 num 是否可被 x 整除。如果余数为 0，则停止。

前任。

mod = 1;
while (mod != 0)
{
mod = num % x;
x++;
}

塔达！质数检查器...不确定是否有比这更快的方法。

于 2013-06-05T07:48:45.480 回答
0

我最近做了一个更快的算法。它可以在几秒钟内轻松地散列出一个 14 位数字。只需将此代码粘贴到任何接受 javascript 代码并运行它的地方。请记住，javascript 的版本必须是本文的最新版本，因为它必须支持 BigInteger 才能执行这些操作。通常最新的浏览器（Chrome、firefox、Safari）会支持这样的功能。但任何人都可以猜测其他浏览器（如 Microsoft IE）是否会正确支持它。

--

该算法通过使用前面提到的一些算法思想的组合来工作。

然而...

该算法实际上是通过可视化素数集并将它们乘以各种不同的值然后对这些值执行各种模运算并使用这些数字创建所有素数的 3d 表示来生成的，从而揭示存在于素数中的真实模式套。

var prime_nums = [2n,3n,5n,7n,11n,13n,17n,19n,23n,29n,31n,37n,41n,43n,47n,53n,59n,61n,67n,71n,73n,79n,83n,89n,97n,101n,103n,107n,109n,113n,127n,131n,137n,139n,149n,151n,157n,163n,167n,173n,179n,181n,191n,193n,197n,199n,211n,223n,227n,229n,233n,239n,241n,251n,257n,263n,269n,271n,277n,281n,283n,293n,307n,311n,313n,317n,331n,337n,347n,349n,353n,359n,367n,373n,379n,383n,389n,397n,401n,409n,419n,421n,431n,433n,439n,443n,449n,457n,461n,463n,467n,479n,487n,491n];

function isHugePrime(_num) {
  var num = BigInt(_num);
  var square_nums = [BigInt(9) ,  BigInt(25) , BigInt(49) ,BigInt(77) , BigInt(1) , BigInt(35) , BigInt(55)];

  var z = BigInt(30);
  var y = num % z;

  var yList = [];
  yList.push(num % BigInt(78));
  var idx_guess = num / 468n;
  var idx_cur = 0;
  while ((z * z) < num) {
      z += BigInt(468);
      var l = prime_nums[prime_nums.length - 1]

         while (l < (z / BigInt(3))) {
                idx_cur++;
                l += BigInt(2);
                if (isHugePrime(l)) {
                    prime_nums.push(l);
                }
      }
      y = num % z;
      yList.push(y);


    }
  for (var i=0; i<yList.length; i++) {
      var y2 = yList[i];
      y = y2;
      if (prime_nums.includes(num)) { return true; }
      if ((prime_nums.includes(y)) || (y == BigInt(1)) || (square_nums.includes(y))) {

                          if ((y != BigInt(1)) && ((num % y) != BigInt(0))) {

                             for (var t=0; t<prime_nums.length; t++) {
                                  var r = prime_nums[t];
                                  if ((num % r) == BigInt(0)) { return false; }
                                }

                              return true;
                            }
                          if (y == BigInt(1)) {
                              var q = BigInt(num);
                              for (var t=0; t<prime_nums.length; t++) {
                                  var r = prime_nums[t];
                                  if ((q % r) == BigInt(0)) { return false; }
                                }


                              return true;

                            }

                       }

    }
  return false;
}
于 2018-09-07T12:04:34.593 回答