mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-09-17, 19:19   #1
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

22748 Posts
Default Lucas-Lehmer Test

On the GIMPS site, there is an example of the LL test. The value tested is 27 - 1. 127.

Why does this example only work with 127?

storm5510 is offline   Reply With Quote
Old 2009-09-17, 19:45   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

How exactly are you modifying it that the example fails to work for other numbers?

http://www.mersenne.org/various/math.php
Quote:
The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2P-1 is prime if and only if Sp-2 is zero in this sequence: S0 = 4, SN = (SN-12 - 2) mod (2P-1). For example, to prove 27 - 1 is prime:
Code:
        S0 = 4
        S1 = (4 * 4 - 2) mod 127 = 14
        S2 = (14 * 14 - 2) mod 127 = 67
        S3 = (67 * 67 - 2) mod 127 = 42
        S4 = (42 * 42 - 2) mod 127 = 111
        S5 = (111 * 111 - 2) mod 127 = 0
Here's a modification of it for p=5 (2p-1=31):
Code:
        S0 = 4
        S1 = (4 * 4 - 2) mod 31 = 14
        S2 = (14 * 14 - 2) mod 31 = 8
        S3 = (8 * 8 - 2) mod 31 = 0
Sp-2=S3=0, hence 2p-1=31 is prime.

Or have I got your confusion all wrong?
Mini-Geek is offline   Reply With Quote
Old 2009-09-17, 23:00   #3
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

22748 Posts
Default

What I experimented with is below:

Code:
S = 4
N = 257

Do
S = ((S * S) - 2) Mod N
Loop While S <> 0
This seems to work for only certain powers of 2. Perhaps that is the point. The value "N" above is not.

Quote:
(It is also possible to start with S(1)=10 and certain other values depending on p.)
This could have been explained a bit more?
storm5510 is offline   Reply With Quote
Old 2009-09-17, 23:17   #4
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

22×3×232 Posts
Default

257 is not a number of the form 2^p-1, and the Lucas-Lehmer test is only defined for numbers of that form. N=2^257-1 would work, though be sure that you're using a language (eg Python) where arithmetic on large numbers is defined correctly - check that 65536*65536*65536*65536 is not equal to zero.

Last fiddled with by fivemack on 2009-09-17 at 23:21
fivemack is offline   Reply With Quote
Old 2009-09-17, 23:17   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1CF816 Posts
Default

Quote:
Originally Posted by storm5510 View Post
What I experimented with is below:

Code:
S = 4
N = 257

Do
S = ((S * S) - 2) Mod N
Loop While S <> 0
This seems to work for only certain powers of 2. Perhaps that is the point. The value "N" above is not.

This could have been explained a bit more?
Huh? 257 is not a Mersenne number. It is 2^8 + 1!!!!! Duh!!!!
Mersenne numbers are 2^p-1 for p prime.

As for explaining why S=10 works as the starting value in addition to
S=4, I can only say that you lack the math to understand an explanation.
(Do you know what the twisted group of GF(p^2) is? Do you even know
what a group or finite field is?)
R.D. Silverman is offline   Reply With Quote
Old 2009-09-17, 23:54   #6
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

100101111002 Posts
Angry

I ask a question and this is the kind of reply I get! I should have known better. I'll never ask anything here again...

storm5510 is offline   Reply With Quote
Old 2009-09-18, 00:18   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

163708 Posts
Default

Quote:
Originally Posted by storm5510 View Post
I ask a question and this is the kind of reply I get! I should have known better. I'll never ask anything here again...

When one asks about a primality test for Mersenne primes, it should
be assumed that the person asking the question knows WHAT
a Mersenne prime is.
R.D. Silverman is offline   Reply With Quote
Old 2009-09-18, 02:20   #8
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102538 Posts
Default

Ignore Silverman, please. I don't understand why 10 works as a starting number as well as 4, but it really doesn't matter here. And yes, you should have noticed that N=257 is invalid for the LL test, but it's a simple mistake. Silverman overreacted, and if you stop asking questions, you'll be overreacting too.

There are two major problems with your code:
1. N is 257, which is not of the form 2^p-1. It is prime and could be used for p, but not for 2^p-1. (e.g. you could use P=257 and N=2^P-1, then run the loop 257-2 times, with each step being mod N)
2. You're not stopping at the right spot. If the number is composite, you'll eventually either enter into an endless loop and run the number forever, or reach 0 at an index besides Sp-2 and inaccurately report the number as prime. If the number is prime, it works just fine.

Last fiddled with by Mini-Geek on 2009-09-18 at 02:24
Mini-Geek is offline   Reply With Quote
Old 2009-09-18, 03:24   #9
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

22·3·101 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
When one asks about a primality test for Mersenne primes, it should
be assumed that the person asking the question knows WHAT
a Mersenne prime is.
2P - 1, where P is any even number. Subtract 1 and it becomes odd, then an exponent of 2.

3, 7, 15, 31, 63, 127, 255 .... 2097151, 4194303, so forth, and so on, what not, and what have you.

Quote:
Ignore Silverman, please.
Gladly...

My mistake was forgetting to remove 257. I was experimenting to see what happened by stepping through the code with "strange" numbers.

I watched it repeat with the same values several times and realized it had to stop sometime.

I am not trying to re-invent the wheel, just learn a thing, or two. When the day comes that this is not possible, then it will be the day I get a rope...

Last fiddled with by storm5510 on 2009-09-18 at 03:58
storm5510 is offline   Reply With Quote
Old 2009-09-18, 04:11   #10
flouran
 
flouran's Avatar
 
Dec 2008

72·17 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I can only say that you lack the math to understand an explanation.
(Do you know what the twisted group of GF(p^2) is? Do you even know
what a group or finite field is?)
Silverman, you are a nitwit. When someone asks for help and IF YOU CAN HELP THEM, then offer suggestions. If you cannot help them (be it due to yours or their mathematical inability), then just do not respond. Simple as that.
flouran is offline   Reply With Quote
Old 2009-09-18, 06:49   #11
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

100101111002 Posts
Question

Be it stupid, or not, here's what I am looking for:

I have an application which I can punch a number into. The purpose is to see if it is a prime number. It doesn't matter what type.

The conventional way is to iterate all the way up to the square root of said number in steps of two, starting at three, while skipping multiples of five.

This can be time consuming if a very large number is entered. Is there a more time-efficient method?
storm5510 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
A second proof for the Lucas-Lehmer Test carpetpool Miscellaneous Math 2 2017-07-30 09:21
Lucas-Lehmer test Mathsgirl Information & Answers 23 2014-12-10 16:25
Lucas Lehmer test question? BMgf Programming 23 2003-12-09 08:52
about Lucas-Lehmer test and Prime 95 Annunaki Math 22 2003-08-05 21:52

All times are UTC. The time now is 19:02.

Thu May 28 19:02:29 UTC 2020 up 64 days, 16:35, 0 users, load averages: 1.66, 1.76, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.