javascript - 实现 Lucas–Lehmer 素性检验的问题

Question

我尝试对 Mersenne 数 ( 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 .