How to resolve the algorithm Lucas-Lehmer test step by step in the zkl programming language

Problem Statement
Step by Step Solution
Sourcecode

Problem Statement

Lucas-Lehmer Test: for

{\displaystyle p}

an odd prime, the Mersenne number

− 1

{\displaystyle 2^{p}-1}

is prime if and only if

− 1

{\displaystyle 2^{p}-1}

divides

S ( p − 1 )

{\displaystyle S(p-1)}

where

S ( n + 1 )

( S ( n )

)

− 2

{\displaystyle S(n+1)=(S(n))^{2}-2}

, and

S ( 1 )

{\displaystyle S(1)=4}

Calculate all Mersenne primes up to the implementation's maximum precision, or the 47th Mersenne prime (whichever comes first).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Lucas-Lehmer test step by step in the zkl programming language

Source code in the zkl programming language

var [const] BN=Import.lib("zklBigNum");	// lib GMP
primes:=Utils.Generator(Import("sieve").postponed_sieve);
fcn isMersennePrime(p){
   if(p==2) return(True);
   mp:=BN(1).shiftLeft(p) - 1; // 2^p - 1, a BIG number, like 1000s of digits
   s:=BN(4); do(p-2){ s.mul(s).sub(2).mod(mp) } // the % REALLY cuts down on mem usage
   return(s==0);
}

mersennePrimes:=primes.tweak(fcn(p){ isMersennePrime(p) and p or Void.Skip });
println("Mersenne primes:");
foreach mp in (mersennePrimes) { print(" M",mp); }

ps,mpOut := Thread.Pipe(),Thread.Pipe(); // how the threads will communicate
fcn(ps){   // a thread to generate primes, sleeps most of the time
   Utils.Generator(Import("sieve").postponed_sieve).pump(ps)
}.launch(ps);

do(4){ // four threads to perform the Lucas-Lehmer test
   fcn(ps,out){ ps.pump(out,isMersennePrime,Void.Filter) }.launch(ps,mpOut)
}
println("Mersenne primes:");
foreach mp in (mpOut) { print(" M",mp); }