A Followup question on Mlucas...

[DeadSpam]

Thank you all for answering my first question...now I have another question about the LL test as run in MLucas...

Do the statistical odds actually increase for a positive result as the number of iterations passed increases?

I'm running a test right now and am 580,000 iterations in...so far, no rounding errors and am churning out 2000 iterations every 50 minutes +- 30 seconds.

It would seem to me that the odds would have to increase, but I don't remember enough statistics to compute HOW much...

Thanks in advance!

[Mini-Geek]

No, it does not. Because of how the LL test works it must complete all iterations before it knows whether it's prime or not.
More reading on LL test:
http://en.wikipedia.org/wiki/Lucas%E...rsenne_numbers
http://mathworld.wolfram.com/Lucas-LehmerTest.html

[R.D. Silverman]

Originally Posted by DeadSpam

Thank you all for answering my first question...now I have another question about the LL test as run in MLucas...

Do the statistical odds actually increase for a positive result as the number of iterations passed increases?
:

Allow me to ask:

To what statistical odds do you refer? The number being tested is either
prime or composite. There are no "odds".

If you refer to the a priori probability of a *randomly selected* value of
2^p-1 being prime, this has nothing to do with the LL test.

I also do not understand you reference to "number of iterations". How
could anyone think that the number of iterations is related to probability in
any way? I need to understand your thinking before I can help. What
probability do you think is related to the number of iterations?

[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

[Mini-Geek]

Originally Posted by R.D. Silverman

Allow me to ask:

To what statistical odds do you refer? The number being tested is either
prime or composite. There are no "odds".

If you refer to the a priori probability of a *randomly selected* value of
2^p-1 being prime, this has nothing to do with the LL test.

I also do not understand you reference to "number of iterations". How
could anyone think that the number of iterations is related to probability in
any way? I need to understand your thinking before I can help. What
probability do you think is related to the number of iterations?

Here's my view of what he meant: "Is it like a factoring attempt to where the longer it's run without stopping itself because it found a factor, the higher chances it's prime?" Or "Is the % done saying how many possible factors it's eliminated?" Meaning that if it's 99% done, 99% of the possible factors have been eliminated as factors, so the chances of it being prime are high.
note to deadspam: Don't take what I'm saying here as what is correct, that's in my first post. What I'm trying to say here is what you said, but in another way so other people understand it.

[cheesehead]

Originally Posted by R.D. Silverman

I also do not understand you reference to "number of iterations".
< snip >
I need to understand your thinking before I can help.

I think most novices can easily be, and usually are, misled by Prime95's use of "iteration" in its user interface to refer both to a single TF division step (constituting a complete test of whether a particular candidate is a factor of the Mersenne number) and to a single L-L iteration (which is only one step within a single modular computation of S(p-2)).

As we've repeatedly seen implied by novices' questions in this forum, an average novice will fairly easily understand that the TF process is a series of tests of multiple individual candidate divisors of a Mersenne number, especially because this obviously parallels the definition of a prime as a number not divisible by any number other than itself and 1. In contrast, the L-L test's ultimate dependence on a division (of S(p-2) by the Mersenne number) is not nearly so clear to a novice.

(I'm tempted to assign significance to the fact that the meaning of the division in L-L is opposite to that in TF -- in TF, a zero remainder signals compositeness, while in L-L a zero implies primeness -- but if one's understanding goes that far, one is unlikely to be fazed by the opposite phases. :)

Novices' questions I've seen repeatedly show that they are thinking that the L-L test is basically a series of tests of individual candidate divisors, as in TF but somehow only modestly different in the detail of its (L-L) supposed "individual tests". This assumed parallel leads directly to misunderstandings.

[DeadSpam]

Ok...

I guess I don't understand just wnat an 'iteration" consists of in the L-L test I am running.

Right now, I am thru 608,000 "iterations", with each 2K outputting that Res64: <Big Hex Number Here>.

In these 600K + iteratons, just WHAT has the program accomplished?

(Yes, I am a 'novice' nut will be able to follow the math if someone explains it...
SLOWLY...lol

Ed

[akruppa]

The Lucas-Lehmer test is pretty much just a huge exponentiation (although in GF(p²), but that's beside the point atm). The Mersenne number is prime if and only if the result of the exponentiation is a particular value, a residue of 0 in case of the Lucas-Lehmer test. What each iteration does is process a bit of the exponentiation, so it keeps getting closer to the final result. Unfortunately, we cannot tell what the final result will be by the intermediate results during the exponentiation, so all we can do is wait for the exponenitation to finish and get the final answer then.

Alex

[m_f_h]

Originally Posted by DeadSpam

Ok...
I guess I don't understand just wnat an 'iteration" consists of in the L-L test I am running.
Right now, I am thru 608,000 "iterations", with each 2K outputting that Res64: <Big Hex Number Here>.
In these 600K + iteratons, just WHAT has the program accomplished?
(Yes, I am a 'novice' nut will be able to follow the math if someone explains it...
SLOWLY...lol
Ed

I'd say it like that : the "LL test for Mp=2^p-1" is nothing else than the computation of ONE SINGLE NUMBER, which we could call X(p), and which is the rest of the division of cosh(2^(p-2) log(2+sqrt(3))) by Mp. If this is zero, p is prime; otherwise not. Basically, that's all.

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. Each of these steps is one of the famous iterations. (Here p = 32 ooo ooo, e.g.)
The RES_64 (which I have never seen printed...) is just some (binary) digits of the number S[n], as a kind of debugging information while the calculation goes on...

This sequence grows extremely fast, but fortunately it is sufficient to keep at each step only the rest modulo 2^p-1, i.e. (roughly said...) about ("only"(!)) the least 10^7 decimal digits.
There digits make up the 8MB file which P95 saves every 30 mins.
So, each iteration corresponds to calculating the square of this "small number" - 2 and taking again the rest mod Mp.

So in some sense, prior to the last step, the program has achieved "nothing" yet!
(Well, one could quite easily see already from the last value, S[p-2], if p is prime. [Namely, if S[p-2] = +/- 2^((p+1)/2) mod Mp.] But from the penultimate, S[p-2], it would be already quite hard, and this would only save 2 iteration in 32 million. OK, that's not the whole information [for non-prime p the last values usually are periodically repeated so one could detect such a "looping" already before, but it's quite impossible to implement.])

[rgiltrap]

Originally Posted by DeadSpam

Ok...

I guess I don't understand just what an 'iteration" consists of in the L-L test I am running.

Right now, I am thru 608,000 "iterations", with each 2K outputting that Res64: <Big Hex Number Here>.

In these 600K + iteratons, just WHAT has the program accomplished?

Ed

I think the easiest analogy is this.

Remember the game people do with flowers ... "She loves me... She loves me not"

LL tests are like that but with a REALLY BIG flower with LOTS of petals.

Each petal you remove is an iteration and the residual is binary (loves me or loves me not). For LL tests the same applies but the residual is a "Big Hex Number".

As you remove the petals (complete iterations) you get closer to knowing the answer, but not any closer to what the answer will be. The answer will not be revealed until the final iteration has occurred. Either she loves you (prime) or not (not a prime).

Of course, even if she does loves you, it is only a matter of time before she leaves you for someone with a bigger PRIME

[jasong]

Originally Posted by rgiltrap

I think the easiest analogy is this.

Remember the game people do with flowers ... "She loves me... She loves me not"

LL tests are like that but with a REALLY BIG flower with LOTS of petals.

Each petal you remove is an iteration and the residual is binary (loves me or loves me not). For LL tests the same applies but the residual is a "Big Hex Number".

As you remove the petals (complete iterations) you get closer to knowing the answer, but not any closer to what the answer will be. The answer will not be revealed until the final iteration has occurred. Either she loves you (prime) or not (not a prime).

That is an awesome analogy. We need more posters like you.