mersenneforum.org  

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

Reply
 
Thread Tools
Old 2005-12-06, 19:34   #1
MS63
 
Oct 2005

22·32 Posts
Default Running LL test from both ends of the sequence?

I am not a mathematician. I have not studied how the LL method works, nor do not understand it.

A frequent question in these forums concerns the use of two (or more) processors to tackle the same candidate simultaneously in order to reduce the total procedure time. The answers are always that it is either minimally useful or cannot be done.

(Now I am going to show my ignorance.)

Would it possible set the LL test running twice on the same prime candidate starting at each end, as it were, and meeting somewhere in the middle?
MS63 is offline   Reply With Quote
Old 2005-12-06, 19:43   #2
John Renze
 
John Renze's Avatar
 
Nov 2005

608 Posts
Default

Quote:
Originally Posted by MS63
Would it possible set the LL test running twice on the same prime candidate starting at each end, as it were, and meeting somewhere in the middle?
No it wouldn't. It's a lot harder to take the square root than it is to square, which is what you would have to do to run LL backwards.

John
John Renze is offline   Reply With Quote
Old 2005-12-06, 19:44   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Default

Quote:
Originally Posted by MS63

(Now I am going to show my ignorance.)

Would it possible set the LL test running twice on the same prime candidate starting at each end, as it were, and meeting somewhere in the middle?
(1) Your question is not well posed. What do you mean by "meeting in the
middle"? Explain how you think one would or could "start at each end"?
And if your answer is "I'm not sure what I mean", then my answer is that
one should never ask a question that one does not understand. Which is
what I suspect that you are doing.

One does not need to be a mathematician to apply a little common sense.
I suggest that you do so.

We have an initial starting value: L_0 = 4. We are trying to compute
a final value: L_n. How do you propose we "start at each end" if we don't
even know what the ending value is???

And it certainly is possible to do FFT's in parallel with little loss in efficiency.
However, we can do Mersenne prime testing with ZERO loss in efficiency
simply by giving separate exponents to separate machines. This is what is
done now.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-06, 20:19   #4
MS63
 
Oct 2005

448 Posts
Default

Thank you, John. Exactly what I was hoping for: A concise reply. While I have no appreciation of its significance (nor do I need to), I understand the explanation.


RD - I made it perfectly clear that I do not understand how the LL test works and that I was demonstrating my ignorance.

Regarding "starting at each end ... and meeting somewhere in the middle", I know exactly what I mean and so would you if you would "apply a little common sense."

Just for your benefit, RD, if I wanted to test 1234567 for primality I could, for example, use a simple arithmetic test to discover if any integer between 2 and SQRT(1234567) was an exact divisor of 1234567. If I chose to I could increase the speed of my test by running it twice, one test starting at 2 and working upwards, the other starting at SQRT(1234567) and working downwards. "somewhere in the middle" the two would converge.

Now I am NOT suggesting that the LL test works like this. In fact I was at pains to make clear that I have no understanding of how it works.

"We have an initial starting value: L_0 = 4. We are trying to compute a final value: L_n. How do you propose we "start at each end" if we don't even know what the ending value is???" means nothing to me.

"FFT" has no meaning to me beyond the words the letters represent.

Congratulations, RD, for once again pointlessly attacking a self-confessed "Ignorant GIMPSer".
MS63 is offline   Reply With Quote
Old 2005-12-06, 20:58   #5
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

100101001012 Posts
Default

Let me quote about the LL test from www.mersenne.org/math.htm

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
Now how could we start at S5? We don't know the answer. In fact, if we did, we wouldn't have to run the test because the only thing we're interested in is the answer to the very last step in the (long) sequence. If it turns out to be 0, the number is prime. Any other value and the number is composite.

Last fiddled with by smh on 2005-12-06 at 21:02
smh is offline   Reply With Quote
Old 2005-12-06, 21:05   #6
MS63
 
Oct 2005

22·32 Posts
Default

Quote:
Originally Posted by smh
Let me quote about the LL test from www.mersenne.org/math.htm

Quote:
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
Now how could we start at S5? We don't know the answer. In fact, if we did, we wouldn't have to run the test because the only thing we're interested in is the answer to the very last step in the (long) sequence. If it turns out to be 0, the number is prime. Any other value and the number is composite.

Now how could we start at S5? We don't know the answer. In fact, if we did, we wouldn't have to run the test because the only thing we're interested in is the answer to the very last step in the (long) sequence. If it turns out to be 0, the number is prime. Any other value and the number is composite.
Clear as mud!

Last fiddled with by MS63 on 2005-12-06 at 21:08
MS63 is offline   Reply With Quote
Old 2005-12-06, 21:06   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

9,791 Posts
Default

Actually, Bob's reply, though perhaps a bit more pointed than necessary, makes perfect sense to anyone who understands the basics of a one-way iterative procedure like the LL test. (I say "one way" because although it is theoretically possible to run it in reverse, that requires both modular square root taking, which is much harder than the modular squaring we use to proceed in the forward direction, and knowledge of the final value, which is impossible to attain without having first run the test in the forward direction.) Your example of trial-division to test for factors is in no way analogous - in trial-dividing to find a factor of N, you can easily calculate floor(sqrt(N)) and work backwards from that, if you like. Better still, you can precompute batches (or ranges) of trial divisors and assign each to a separate processor - the problem is trivially parallelizable. Generalize "meeting in the middle" to "testing all primes <= floor(sqrt(N))" and there you go.

In the LL test, we start with some appropriate initial value (e.g. 4), then do a bunch of square-and-subtract-two steps. So far, no problem. But even if we could somehow run the test in reverse (add two, take square root) as fast as forward, what does "meeting in the middle mean" if we don't know the ending value from which we are supposed to run the "upper half" test in reverse? That's why your query is ill-posed.

Oh, and in response to your other point, "FFT" stands for "Fast Fourier Transform" - it's the algorithm we use to efficiently effect the large-integer multiplies needed for big-number primality testing.

Last fiddled with by ewmayer on 2005-12-06 at 21:09
ewmayer is offline   Reply With Quote
Old 2005-12-06, 21:15   #8
MS63
 
Oct 2005

22·32 Posts
Default

Quote:
Originally Posted by ewmayer
... anyone who understands ...
Which I don't, which is EXACTLY my point. Therefore my question is perfectly valid, not "ill-posed".

As I said, I know the words that "FFT" stand for, but nothing beyond that.
MS63 is offline   Reply With Quote
Old 2005-12-06, 22:05   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by MS63
Thank you, John. Exactly what I was hoping for: A concise reply. While I have no appreciation of its significance (nor do I need to), I understand the explanation.


RD - I made it perfectly clear that I do not understand how the LL test works and that I was demonstrating my ignorance.

Regarding "starting at each end ... and meeting somewhere in the middle", I know exactly what I mean and so would you if you would "apply a little common sense."

Just for your benefit, RD, if I wanted to test 1234567 for primality I could, for example, use a simple arithmetic test to discover if any integer between 2 and SQRT(1234567) was an exact divisor of 1234567. If I chose to I could increase the speed of my test by running it twice, one test starting at 2 and working upwards, the other starting at SQRT(1234567) and working downwards. "somewhere in the middle" the two would converge.

Now I am NOT suggesting that the LL test works like this. In fact I was at pains to make clear that I have no understanding of how it works.

"We have an initial starting value: L_0 = 4. We are trying to compute a final value: L_n. How do you propose we "start at each end" if we don't even know what the ending value is???" means nothing to me.

"FFT" has no meaning to me beyond the words the letters represent.

Congratulations, RD, for once again pointlessly attacking a self-confessed "Ignorant GIMPSer".
You've got no business asking questions of this nature if your ignorance is
that total.

And my response about starting and ending values was quite clear.
You propose to start at "the end". But "the end" is the OBJECTIVE OF
THE COMPUTATION AND IS UNKNOWN AT THE BEGINNING. This should
be clear even without knowledge of how the algorithm works. Clear that
is to anyone with two working brain cells.

You failed to do even minimal reading of the subject material. Nothing is
quite so irritating to a teacher as a student who asks questions without
having done required homework and preparation. Maybe when you grow up
you will understand this.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-06, 22:14   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by MS63
Clear as mud!

This explanation is quite elementary and quite clear.

It is not just that you are ignorant of the algorithm,
you seem unable to read even a simple description of it. Go away until
you earn some basic mathematics and some basics of computer algorithms.

And before you get upset, this is how any teacher handles a student who
lacks the pre-requisites to study a subject.
R.D. Silverman is offline   Reply With Quote
Old 2005-12-06, 22:17   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31·43 Posts
Default

The following is my interpretation of the original poster requirements.

Suppose that we want to run the algorithm in reverse, starting with Sp-2 = 0 (supposing that the number is prime) and we know how to perform the modular square root at the same speed as multiplication (of course, if you know such a method, please let me know).

So the original poster wants to start computing S0 = 4, S1, S2, etc. and at the same time Sp-2 = 0, Sp-3, etc. up to S(p-3)/2. Then we check whether both numbers are equal and if they are, the Mersenne number in question is prime.

I think there is a big problem here. What of the two square root do we have to compute in the reverse computation? It appears that there are two possible values of Sp-3, four values for Sp-4, eight values for Sp-5, etc. How do we know which is the correct one?
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SIGSEGV in xi3eK8 running torture test GordonWade Information & Answers 10 2018-02-18 00:07
Can I just start Prime95 by running torture test? marks9GIMPS Information & Answers 5 2011-06-05 18:44
Dual Core and running the same test..? Unregistered Information & Answers 1 2008-03-01 15:02
Prime95 crashing while running blend test day61 Hardware 1 2007-01-30 12:03
Running a LL test on 2 different machines lycorn Software 10 2003-01-13 19:34

All times are UTC. The time now is 13:37.

Sun Oct 25 13:37:01 UTC 2020 up 45 days, 10:47, 0 users, load averages: 1.60, 1.69, 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.