Message Boards Message Boards

0
|
1551 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
POSTED BY: Michael Gmirkin
3 Replies

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

POSTED BY: Daniel Lichtblau
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

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