LucasLehmer.frink

View or download LucasLehmer.frink in plain text format


// Implements the Lucas-Lehmer test for Mersenne primes.
// This test is sufficient to prove primality.
//
// To be a Mersenne prime, n must be prime.  This function does not first
// test that, as it is assumed that some sort of preliminary sieving has
// occurred.

// NOTE:
// As of the 2005-11-12 release of Frink, the isPrime[x] routine automatically
// detects if a number is of the form 2^n-1 and uses this more efficient
// Lucas-Lehmer test, rather than the usual Rabin-Miller tests.

// Returns true if 2^n - 1 is prime, false otherwise.
isMersennePrime[n] :=
{
   m = 2^n-1
   s = 4

   for i = 2 to n-1
      s = (modPow[s,2,m] - 2) mod m  // modPow[base,exp,m] is base^exp mod m

   // Return true (prime) if s is equal to zero, false otherwise.
   return s==0
}


View or download LucasLehmer.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17959 days, 13 hours, 20 minutes ago.