 mersenneforum.org > Math Running LL test from both ends of the sequence?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2005-12-06, 19:34 #1 MS63   Oct 2005 1001002 Posts 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?   2005-12-06, 19:43   #2
John Renze

Nov 2005

24·3 Posts 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   2005-12-06, 19:44   #3
R.D. Silverman

Nov 2003

746010 Posts 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.    2005-12-06, 20:19 #4 MS63   Oct 2005 22·32 Posts 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".   2005-12-06, 20:58   #5
smh

"Sander"
Oct 2002
52.345322,5.52471

4A516 Posts 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   2005-12-06, 21:05   #6
MS63

Oct 2005

22×32 Posts 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   2005-12-06, 21:06 #7 ewmayer ∂2ω=0   Sep 2002 República de California 101101011010002 Posts 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   2005-12-06, 21:15   #8
MS63

Oct 2005

22×32 Posts 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.   2005-12-06, 22:05   #9
R.D. Silverman

Nov 2003

746010 Posts 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.   2005-12-06, 22:14   #10
R.D. Silverman

Nov 2003

22×5×373 Posts 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.   2005-12-06, 22:17 #11 alpertron   Aug 2002 Buenos Aires, Argentina 5·269 Posts 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?   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post GordonWade Information & Answers 10 2018-02-18 00:07 marks9GIMPS Information & Answers 5 2011-06-05 18:44 Unregistered Information & Answers 1 2008-03-01 15:02 day61 Hardware 1 2007-01-30 12:03 lycorn Software 10 2003-01-13 19:34

All times are UTC. The time now is 18:46.

Sat Apr 10 18:46:37 UTC 2021 up 2 days, 13:27, 1 user, load averages: 1.21, 1.53, 1.61

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.