Message Boards Message Boards

0
|
1526 Views
|
3 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Can the Lucas-Lehmer primality test be implemented in Wolfram Language?

Posted 9 months ago

So, I recently ran across a couple lovely YouTube videos on Perfect Numbers and their relationship to Mersenne Primes, and decided to fiddle around with some stuff in Excel.

Now I'm wondering ... asking for a friend ... cough ... is it possible to implement some kind of efficient Lucas Lehmer testing in Mathematica either as some specific Mathematica code in a notebook or as like a core function?

Couldn't seem to find much on it. Not really familiar with prime testing or how exactly the Lucas-Lehmer test works. I assume it's some kind of advanced sieve or something that goes through a number of divisions by prime values to eliminate all possible prime divisors, or some such?

I guess part of what I wonder with respect to Mathematica is whether or not it could implement some kind of logging or start/stop type routine where it can "pick up where it left off" if interrupted ,whether due to a human closing the program, the kernel freezing, program crashing, computer rebooting, etc. IE, one wouldn't have to literally "start over from the beginning" in case of a fault or accidental action of some kind?

I know Mathematica has PrimeQ and ProvablePrimeQ functions. But, it seems like when you run them on a really large prime candidate, it just ... sits there presumably evaluating in the back ground ... but presumably that could take hours, weeks, months, years, depending how large a number one is evaluating? Like how long would a billion digit prime take to "evaluate"?

Would be cool if one could devise some kind of like logged solution that'll save its progress at regular intervals, pick up where it left off, allow some kind of inspection of what work it's already done, etc. whether it's like saving stuff to a table or some kind of log file, database, or whatever...

Just kinda' thinking out loud, as far as wish-list type stuff goes. ^_^

POSTED BY: Michael Gmirkin
3 Replies

It is certainly possible to implement what you want, but it takes a lot of time and extensive programming knowledge.I not a programer with this skills.

Code is slow and naive. Using: Aria AI in Opera borwser give me:

 LucasLehmerTest[n_Integer] := 
  Module[{s = 4, i}, 
   For[i = 3, i <= n, i++, s = Mod[s^2 - 2, 2^n - 1];];
   If[s == 0, True, False]]

LucasLehmerTest[127]
(*True*)

primes = {3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701};
Table[LucasLehmerTest[primes[[j]]], {j, 1, Length@primes}] // AbsoluteTiming

(*{6.71683, {True, True, True, True, True, True, True, True, True, True,
   True, True, True, True, True, True, True, True, True, True, True, 
  True, True, True}}*)

Regards M.I.

POSTED BY: Mariusz Iwaniuk
Posted 9 months ago

The is a wonderful piece on the Wolfram blog "Mersenne Primes and the Lucas-Lehmer Test" (https://blog.wolfram.com/2016/09/30/mersenne-primes-and-the-lucas-lehmer-test/) which you may find very helpful.

I'm no expert in this area, but I recall there is a trick involving binary expansions of intermediate results which is much faster than looping over a call to Mod[]. In addition, I imagine it would be straightforward to save intermediate results to disc, to make it easy to resume calculations. IIRC this is how the Great Internet Mersenne Prime Search (GIMPS) works.

Good luck. JS

POSTED BY: John S

A reference implementation of a recent variant can be found in this prior Community thread.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract