Running LL test from both ends of the sequence?

[MS63]

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?

[John Renze]

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

[R.D. Silverman]

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.

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

[smh]

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

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:

		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.

[MS63]

Originally Posted by smh

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

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!

[ewmayer]

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.

[MS63]

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.

[R.D. Silverman]

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]

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.

[alpertron]

The following is my interpretation of the original poster requirements.

Suppose that we want to run the algorithm in reverse, starting with S_p-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 S₀ = 4, S₁, S₂, etc. and at the same time S_p-2 = 0, S_p-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 S_p-3, four values for S_p-4, eight values for S_p-5, etc. How do we know which is the correct one?