Newbie question

[pjedmond]

Sorry if this is a daft Q, but this is my first LL effort. I presume that the Prime 95 software stops the moment it actually shows that the number is not prime? I'm at 84% of the LL tests now, and it's taking a very long time! I guess another week or so at this rate. Is it normal to take this long?

[David]

Yes, the program will stop once it knows that the number is not prime-once it gets to 100%. Depending on the speed of your computer and the exponent you're testing, it can take a long time to finsih testing an exponent. You can check out the benchmark page at http://www.mersenne.org/bench.htm to see if your computer is performing as well as it should.

[cheesehead]

Originally Posted by pjedmond

I presume that the Prime 95 software stops the moment it actually shows that the number is not prime?

Expanding on David's answer:

The Prime95 LL test always has to be completed to the 100% level in order to determine whether the number is prime or not prime. The LL test cannot produce an answer, either way, until it is 100% complete, and does not normally stop before that point.

In contrast, trial factoring might find a factor (and thus show that the number is not prime) at any time in its progress to 100%. Trial factoring then would stop as soon as it found a factor, whether that was at 59%, 72%, 99%, or whatever.

As with LL testing, P-1 factoring, which works on different principles than trial factoring, has to proceed to its 100% level in order to determine whether it has found a factor.

I'm at 84% of the LL tests now, and it's taking a very long time! I guess another week or so at this rate. Is it normal to take this long?

Yes, depending on how large a number you're testing, how fast a computer you're using, and what fraction of each day your computer is running Prime95.

We're dealing with very, very large numbers, millions of digits long, here in GIMPS; even though you're using the fastest LL testing software in existence, it still takes a while to test each multi-million-digit number. If the LL tests were faster, someone would've already done them before now. :-)

[Deamiter]

Just being anal, but in response to Cheesehead's explanation, after a trial factoring finds a factor, it's not uncommon for it to go further and look for another. I guess it's useful somehow, but the server only displays the larger one either way.

[David]

after a trial factoring finds a factor, it's not uncommon for it to go further and look for another.

Starting with version 20.3, prime95 no longer searches for smaller factors. Here is a quote from the whatsnew.txt file:

Prime95 no longer searches for a smaller factor when trial factoring discovers a factor. The reasons are two-fold. 1) Version 19 had a bug where stopping and restarting the program bypassed the search for smaller factors. Thus, my database may already be missing smaller factors. 2) As we factor larger exponents to a deeper depth it may no longer be a quick job to determine if there are smaller factors. Note, that version 20 will still look for smaller factors if you are looking for factors below 2^60 with the FactorOverride option in undoc.txt.

[pjedmond]

1.My understanding is that once the LL tests begin, they have to go all the way to 100%? There is no condition (other than an error or user intervention?) that will stop this.
2.What happens if a test at say 45% shows that the number is not prime. Can it stop then or is this totally impossible?
3.After the LL iterations, is it over? or are there more phases? I suspect not from what I've read...but this really takes a long time to check one number!

Sorry if these are obvious questions, but until I've actually seen one process complete, I really haven't a clue what to expect. I've also had a number of really wierd problems relating to running the code stand-alone without a network connection (these have been emailed with info to the person responsible for the code), and now that I've got a connection, I've been having a few confidence issues with the code.

Many thanks for any replies to the above 3 Qs.

[Kevin]

To drive it home, the test must go to 100% and will not be completed until then. Without getting into the details of a LL test (which i don;t fully grasp myself), it basically calculates a recursive series, and if the p-2 th element (where p is the exponent) is 0, then 2^p -1 is prime. Since it is recursive series, you have to find the 1st element, then use that to find the 2nd, then use that to find the 3rd....etc until you find the p-2 th element.

[cheesehead]

Originally Posted by pjedmond

1.My understanding is that once the LL tests begin, they have to go all the way to 100%? There is no condition (other than an error or user intervention?) that will stop this.

Correct.

2.What happens if a test at say 45% shows that the number is not prime.

The LL test is a fundamentally different kind ot mathematical test than trial factoring. It may take a look at the actual mathematics involved to get a clear understanding of this difference, but let me try an explanation without getting too technical:

Trial factoring involves trying to divide the Mersenne number by zillions (where z = "m", "b", "tr", "quadr", ... or whatever) of candidate factors in order to see whether any one of them divides evenly with no remainder. (Actually, Prime95 uses several shortcuts to accomplish this testing faster than it could by just blindly divide all those zillions of times ... but I said I'd not get too technical, so just trust for now that it does what I'm saying, even if not necessarily in a simple straightforward fashion.)

Prime95 tries one candidate factor, then another, then another, then ... until either it finds one that divides the Mersenne number evenly or it reaches the upper limit of candidate factors to try. When it reports its percentage progress in trial factoring, it is referring to the percentage of the zillions of candidate factors in the range being tested that it had tried so far. After it reaches that 45% mark, for example, it might find that the very next candidate factor it tries succeeds, and it finishes without having to try the remaining 55% of the zillions.

But the LL test (and, to a certain extent, P-1 factoring -- but don't push the parallel too far) is NOT trying one possibility after another until finding one that works, but instead is performing a single long chain of calculation consisting of millions of steps. These millions of steps (iterations) are not independent possibilities like the zillions of candidate factors, but instead are sequential links in a mathematical chain that must be 100% completed in order to be useful.

When Prime95 reports its percentage progress in an LL test, it is referring to the percentage of the complete chain of steps that it has completed so far.

Each LL step/iteration/link can only be calculated after the preceding LL step/iteration/link is calculated. The final, and ONLY the final, step/iteration/link gives us the yes/no answer to the question, "Is this Mersenne number prime?" That final step/iteration/link in the LL test can be calculated ONLY after all preceding steps/iterations/links have been completely calculated, in sequential order.

It the LL test were to stop after, say, it was 45% through, the step that had just been completed would not tell us anything useful in regard to whether the Mersenne number is prime. That step's only usefulness is to provide the starting point for the next sequential step/iteration/link. Only the final LL step tells us the prime/nonprime answer.

So, to answer your question, an LL test at 45% will never show that the number is not prime, because it cannot know whether the number is prime until it is 100% complete. Only the very last, final, ultimate step in the multi-million-step LL process gives us a prime/nonprime answer.

Can it stop then or is this totally impossible?

"It" (the LL test) can't stop before it is 100% complete, because its one and only answer comes from its last, final step. You might interrupt the LL test at 45%, but what you'd have is an interrupted LL test with no answer, whose only value would be to enable performing the remaining 55% before producing a prime/nonprime answer.

3.After the LL iterations, is it over?

Yes.

or are there more phases?

No, not for the LL test. P-1 factoring has two stages, but the L-L test does not.

...but this really takes a long time to check one number!

Yes, it does.

But if you try calculating how long it would take trial factoring to completely determine whether a Mersenne number were prime, you'd find that it would require much, much longer than the age of the universe.

So LL testing is much, much faster than trial factoring for the purpose of definitely determining whether a Mersenne number is prime. But LL testing cannot tell us what are the factors of a composite Mersenne number.

[smh]

The math page gives more information about what the program actually does.

From that page:

The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2^P-1 is prime if and only if S(p-2) is zero in this sequence: S(0) = 4, S(N) = S(N-1)^2 - 2 mod 2^P-1. For example, to prove 2^7 - 1 is prime:
[list] 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[/list:u]

<edit>
Changed the error stated below. It was my fault, copy/paste doesn't work that well with superscript.
</edit>

[cheesehead]

Thanks for the math page link, smh.


One small correction:

... if and only if S^p-2 is zero ...

should be

... if and only if S(p-2) is zero ...