实施 Lucas–Lehmer 素性检验的问题

Question

我尝试对梅森数 (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test) 实施 Lucas–Lehmer 检验 (LLT) 素性检验。它应该是多项式的，因此速度很快。这是我的代码：

function countPrimeNumberWithDigits(numberOfDigits)
    {
        if(numberOfDigits < 1)
        {return "Please give a valid input!";}

        var shouldBeMoreThanThis = Math.pow(10, numberOfDigits-1), n = 3, M = countMWithIndex(n);
        while(M < shouldBeMoreThanThis)
        {
            n += 2;
            M = countMWithIndex(n);
        }

        console.log(n);

        while(true)
        {
            var S = 4, k = 1;
            M = countMWithIndex(n);

            while(k != n - 1)
            {
                S = (S*S - 2)%M;
                k +=1;
            }

            if(S!=0)
            {n+=2;}
            else
            {break;}
        }

        return "Prime number: " + countMWithIndex(n);
    }

function countMWithIndex(n)
    {return Math.pow(2, n) - 1;}

这里是尝试使用上面实现的算法： https://oobarbazanoo.github.io/findPrimeNumberWithSpecifiedQuantumOfDigits/

当我尝试输入小于 7 的数字时，一切正常，但当我尝试询问至少 7 位的素数时，程序就出错了，没有给出答案。

请帮帮我。我的算法实现有什么问题或者我的程序本身有什么问题？

Answer 1

如果我运行 https://repl.it/languages/javascript 上的代码进行了此更改：

S = (S*S - 2 + M)%M;

然后它完成（看似）任意数量的数字。但是，结果似乎不正确：它输出的非素数位数比要求的多。

问题是 javascript 可以对负结果求模。例如，-2 % 5 将是 -2。这在数学上是正确的，但大多数计算机科学算法都需要正值，因此在这种情况下 3。

在该公式中添加 M 将确保无论语言怪癖如何，结果都是肯定的。

结果不正确的问题可能是由于您没有遵循此要求：

The Lucas–Lehmer test works as follows. Let Mp = 2**p − 1 be the Mersenne number to test with p an odd prime.

p 你的代码里有 n 。你在任何地方都无法确保 n 是素数。

然后还有就是javascript的整数类型可能不够大。 n 大于 23，它开始达到极限。例如，不存在 7 位数的梅森素数。接下来是10位数字，即2**31 - 1.

您将无法在（纯）javascript 中找到它，因为计算涉及 2**31 - 1、which exceeds the bounds of javascript's integers.

的平方

实施 Lucas–Lehmer 素性检验的问题

Problems with implementing Lucas–Lehmer primality test

javascript

algorithm

primes