- **Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=8*)

- - **Running LL test from both ends of the sequence?**
(*https://www.mersenneforum.org/showthread.php?t=5096*)

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 [b]starting at each end[/b], as it were, and meeting somewhere in the middle? |

[QUOTE=MS63]
Would it possible set the LL test running twice on the same prime candidate [b]starting at each end[/b], as it were, and meeting somewhere in the middle?[/QUOTE] 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 |

[QUOTE=MS63]
(Now I am going to show my ignorance.) Would it possible set the LL test running twice on the same prime candidate [b]starting at each end[/b], as it were, and meeting somewhere in the middle?[/QUOTE] (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. :yucky: 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??? :censored: 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. :squash: |

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

Let me quote about the LL test from [url]www.mersenne.org/math.htm[/url]
[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[/code][/quote]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 [B]only[/B] 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. |

[QUOTE=smh]Let me quote about the LL test from [url]www.mersenne.org/math.htm[/url]
[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[/quote] 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 [B]only[/B] 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.[/QUOTE] Clear as mud! |

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

[QUOTE=ewmayer]... anyone who understands ...[/QUOTE]
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. |

[QUOTE=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".[/QUOTE] 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. |

[QUOTE=MS63]Clear as mud![/QUOTE]
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. |

The following is my interpretation of the original poster requirements.
Suppose that we want to run the algorithm in reverse, starting with S[sub]p-2[/sub] = 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 S[sub]0[/sub] = 4, S[sub]1[/sub], S[sub]2[/sub], etc. and at the same time S[sub]p-2[/sub] = 0, S[sub]p-3[/sub], etc. up to S[sub](p-3)/2[/sub]. 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 S[sub]p-3[/sub], four values for S[sub]p-4[/sub], eight values for S[sub]p-5[/sub], etc. How do we know which is the correct one? |

All times are UTC. The time now is 18:50. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.