A Followup question on Mlucas...

[cheesehead]

Originally Posted by cheesehead

the L-L test's ultimate dependence on a division (of S(p-2) by the Mersenne number)

Originally Posted by m_f_h

For several different reasons this number is called S[p-1].
And it is calculated by repeating p times the formula S[n+1]=S[n]²-2, starting with S[1]=4.

For clarification to novices, it should be noted that my reference to S(p-2) is to the same number that m_f_h calls S(p-1); the difference is that I was assuming 0-origin for S-value indices (i.e., S(0)=4), whereas m_f_h was using 1-origin (i.e., S(1)=4).

Where m_f_h refers to "the penultimate, S[p-2]", that is what I would have called S(p-3).

Originally Posted by m_f_h

And it is calculated by repeating p times the formula S[n+1]=S[n]²-2

However, there m_f_h meant, instead, "... by repeating p-2 times ...".

[cheesehead]

Look at all this huffing-and-puffing by folks who actually (or partially, in my case ) do understand the Lucas-Lehmer test!

Is it any wonder that novices get confused?

[Mini-Geek]

Originally Posted by cheesehead

Look at all this huffing-and-puffing by folks who actually (or partially, in my case ) do understand the Lucas-Lehmer test!

Is it any wonder that novices get confused?

Yeah, that's partially why I linked to the wiki and mathworld links on the LL test. I was pretty sure there'd be a big discussion on this, so I gave those links so that DeadSpam (the original poster) would have something to look at that didn't argue with itself.

[m_f_h]

Originally Posted by Mini-Geek

I was pretty sure there'd be a big discussion on this, so I gave those links so that DeadSpam (the original poster) would have something to look at that didn't argue with itself.

• It's (now : was) not really a discussion, but a variety of explanations.
• I would regret if I had missed the "big flower" explanation - really great ! In view of that I'd almost withdraw my own explanation (but DeadSpam asked for "some" math, nevertheless).
• p vs p-1 vs p-2 : Of course, not p (as I wrote for simplicity - as I also wrote 32,000,000 which has never been tested by GIMPS...), but (p-2) iterations are needed (or p-3 if you start with 14, or p-4 if you start with 194, or p-5 if....) But this is somehow irrelevant. If you are in doubt about +/- 1, you can also do a couple more, and check if the result is equal to 2 (which comes after 0 and does not change any more)... [PS: and when I said "penultimate" I actually meant S[p-3], which is S(p-4) in the other notation.]
• I think DeadSpam could have found the links to Wikipedia or MathWorld etc, but maybe he didn't want to read through all the preliminaries up to reaching the core issue of the computation.

[R.D. Silverman]

Originally Posted by akruppa

I think the question was meant as Mini-Geek interpreted it: it assumed that the LL test can somehow tell half-way through that the number being tested is composite and stop there. But that is not how it works, as Mini-Geek already pointed out.

Alex

However, I still fail to understand the following:

The LL test says that if the result of a particular computation is 0, then the
number is prime.

The details of that computation are irrelevent.

How can anyone be led to even ask the question:

"If one only does part of the computation, does this make it more likely that
the result is true"??? [the result being that the number is prime]

This is, in essence, what the O.P. asked.

I'd like to understand the thought process that might lead someone to
ask about a PARTIAL computation leading to some kind of conclusion about
the ENTIRE computation.

I guess that I just don't understand how people think. What might lead
someone who is told "If A then B" to somehow ask "What about C" when
the statement says nothing about C??

Suppose we had a computation that said: if x^17 = 0 mod N, then N is
prime. How could anyone be led to ask about (say) x^8 mod N?? What
might cause someone to believe that the value of x^8 gives useful
information about the final conclusion? The computation says x^17, not
x^8 mod N gives the answer. Is this a question of READING
comprehension????

I find quite often that the problems beginners and naiive people have with
math is not a lack of mathematical comprehension, but rather of READING
comprehension.

[Mini-Geek]

Originally Posted by R.D. Silverman

I find quite often that the problems beginners and naiive people have with
math is not a lack of mathematical comprehension, but rather of READING
comprehension.

I think it's one of three things:
reading comprehension problems
wanting "instant gratification", they skipped over the relevant parts to finish reading about it faster
or they just never looked it up at all before asking.

[m_f_h]

Originally Posted by Mini-Geek

I think it's one of three things:
reading comprehension problems
wanting "instant gratification", they skipped over the relevant parts to finish reading about it faster
or they just never looked it up at all before asking.

I also think it's an "instant gratification" problem (which may lead to the third situation).
Today, young(not only, but easiest) people are conditionned by "the system" to be good consumers, i.e. to think the "I want it, and I want it now" way. This applies as well to buying things (what if the started thinking : "why do I need this ? do I really need this ?" - they would buy less than half of all the stuff they buy ! Where for do they really need things like the (n+1)st playstation or plasma screen or mobile phone ?) as well as in education.

You also notice that in the approach of students to mathematics but I believe to other subjects. They know they have to spend a given amount in lessons and/or training sessions, but apart from that, they are not taught to spend hours and hours on understanding a problem. If they cannot do the exam at the end of the course, it's the instructor's fault, not theirs. If up to high school the method is "learning by playing around" and never "learning by working hard", how could that change when entering university ?

I think we cannot blame our youth for that (at least only to a small extend). Whom we can blame for that, would be maybe the parents (insofar as they are not yet sufficiently well-conditioned), but first and foremost, the government, or ministry of education. But... it seems the country needs good consumers more than good mathematicians or good engeneers or any other competent people. At least this is true for the short-range reasoning (time scale = time between two elections).
But this is a "democratic" choice. (That word's real significance had already been well understood by the ancient Greek philosophers.)

[m_f_h]

Originally Posted by R.D. Silverman

How can anyone be led to even ask the question:

"If one only does part of the computation, does this make it more likely that
the result is true"??? [the result being that the number is prime]

Well, for some methods (trial factoring, "running ellicptic curves",...) this IS true! You eliminate more and more possibilities and get closer to the result. If instead of the LL test we'd do tiral factoring successively up to 67,68,69,......p/2 bits, it would be less and less probably to have a composite number, up to probability 0. And, before reaching p/2 bits, you DID "achieve" something: the statement "Mp has no factors smallen than 2^k".
So prior to knowing (i.e. reading) what the LL test actually does, this is a "valid" question,
so we tried to provide an extremely oversimplified answer, which clearly explains that "nothing is known", in the case of this particular test, before reaching the end.

[R.D. Silverman]

Originally Posted by m_f_h

Well, for some methods (trial factoring, "running ellicptic curves",...) this IS true! You eliminate more and more possibilities and get closer to the result.

No. You don't. You are bandying about some vague concepts.

For LL, the "result" is a statement of the form "If A then B".

This is NOT true for trial division or ECM.

For a given 2^p-1, One can NOT say: "By trial division, 2^p-1 has no
factors less than X, therefore the probability that 2^p-1 is primes is Z".

2^p-1 is prime either with probability 0 or 1.

All trial division says is: "If 2^p-1 has no factors less than X, then 2^p-1
has no factors less than X": a tautology. One CAN say: "I have
trial divided 2^p-1 to X and found no factors, therefore I have done
Z% of the work needed to factor 2^p-1 by trial division". [where Z depends
on X and p].

But one can say the same of the LL test. One CAN say "I have
performed k iterations, therefore I have done k/(p-2) of the work needed
tp determine if this number is prime". But this says NOTHING about
the "probability" of the number being prime. It simply says one has
done some percentage of the required computation.

For ECM [run on a *known* composite] , all one can say after a number of
trials is that the probability of there being a factor less than X is some value Z. But this really does not get you closer to the *deterministic* goal of
factoring the composite.

You are comparing totally different things. The concepts do not carry
over from one problem to the other.

[ewmayer]

All this debate seems to boil down to the fundamental confusion some beginners have with the profound difference between factorial and nonfactorial compositeness tests.

To some degree that's understandable, but anyone who is savvy enough to post to an online forum is also perfectly capable of doing a little background reading (either on the web or using one of those musty old "book" thingies) to educate themself on the basics. How hard can googling "lucas lehmer test" be?

I'll stop now, lest I be accused of "huffing and puffing."

[davieddy]

Originally Posted by R.D. Silverman

For a given 2^p-1, One can NOT say: "By trial division, 2^p-1 has no
factors less than X, therefore the probability that 2^p-1 is primes is Z".

One can and does say exactly that.
The probability that 2^p-1 is prime when no factor
has been found up to x bits is~ x/(gamma*p)
where gamma is Euler's constant