Problems with implementing Lucas–Lehmer primality test

Question

I try to implement the Lucas–Lehmer test (LLT) primality test for Mersenne numbers (https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test). It should be polynomial and hence fast. Here is my code:

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;}

Here is attempt to use the algorithm implemented above: https://oobarbazanoo.github.io/findPrimeNumberWithSpecifiedQuantumOfDigits/

When I try number of digits which is less than 7 everything is okay, but when I try to ask for prime number with at least 7 digits the program just stumbles and doesn`t give an answer.

Please, help me. What is wrong with my algorithm implementation or what is wrong with my program itself?

Answer 1

If I run the code on https://repl.it/languages/javascript with this change:

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

Then it finishes for (seemingly) any number of digits. However, the results seem incorrect: it outputs non-primes with more digits than requested.

The problem is that javascript can evaluate modulo to negative results. For example, -2 % 5 will be -2. This is mathematically correct, but most computer science algorithms require positive values, so 3 in this case.

Adding M in that formula will ensure that the result is positive regardless of language quirks.

The problem with incorrect results is likely due to the fact that you do not follow this requirement:

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

The p there is the n in your code. Nowhere do you ensure that n is prime.

Then there is also that javascript's integer type might not be big enough. With n larger than 23, it starts to reach its limits. For example, there is no Mersenne prime with 7 digits. The next is with 10 digits, which is 2**31 - 1.

You won't be able to find it in (pure) javascript however, because the computation involves squaring 2**31 - 1, which exceeds the bounds of javascript's integers.