why not stop when composite is prove?
 

Why does the prime95 program has to complete the full 100% checking when it finds BEFORE that the mersenne Number is Composite?
When you want to find new primes as fast possible, stop checking when you iknow it is NOT a prime!

Could someone explain why the 100% is necessarry?

Re: why not stop when composite is prove?
 

[QUOTE][i]Originally posted by mdjvz [/i]
[B]Why does the prime95 program has to complete the full 100% checking when it finds BEFORE that the mersenne Number is Composite?
When you want to find new primes as fast possible, stop checking when you iknow it is NOT a prime!

Could someone explain why the 100% is necessarry? [/B][/QUOTE]

If we know the number is composite (ie, a factor of that number is found) we will not perform a Lucas Lehmer (LL) test.

If no factors of a number are known, we don't know if it's prime or not. To find out we'll have to perform a LL test. With this test you'll only find out if a number is prime or composite after performing the very last step. The percentage you see in the prime95 output is just how far the test is currentely.

for more information about a LL test i suggest you read [url]http://www.mersenne.org/math.htm[/url]

Re: why not stop when composite is prove?
 

[QUOTE][i]Originally posted by mdjvz [/i]
[B]Why does the prime95 program has to complete the full 100% checking when it finds BEFORE that the mersenne Number is Composite?
When you want to find new primes as fast possible, stop checking when you iknow it is NOT a prime!
[/B][/QUOTE]

Can you give an example of this happening?

Note that TWO fully-matching independent Lucas-Lehmer tests are required for each exponent (unless a factor was found), because the error rate for the result is between 3.5-4.0%, averaged over all the machines in the project. So we want to make sure we don't miss a prime due to the first test having an error.

Re: why not stop when composite is prove?
 

[QUOTE][i]Originally posted by mdjvz [/i]
[B]Why does the prime95 program has to complete the full 100% checking when it finds BEFORE that the mersenne Number is Composite? [/B][/QUOTE]

Prime does a few different tests to determine if a specific Mersenne number is prime or not.

First, it does Trial Factoring - if it finds a factor, it immediately stops and reports that factor. This is typically run for all factors under 2 ^ 67 (varies somewhat with the size of the Mersenne number).

Second, *if* the Trial Factoring step does not find a factor, it does a "P-1" and "P-2" step, to look for somewhat larger factors. If it finds a factor in one of those steps, it immediately stops and reports that factor.

Finally, IF none of the above steps finds a factor, Prime starts a LL test on the Mersenne number - this is a VERY LONG computation, and it has to go through THE WHOLE COMPUTATION before it can say "yes, this number is prime" or "no, this number is not prime".

The Trial Factor and P-1/P-2 steps are intended to save time by quickly weeding out Mersenne numbers that happen to have small factors.

The percentage indicator / iteration count vs. total iterations indicator during the LL test is *strictly* telling you how far along on the SINGLE VERY LONG LL test that Prime has gotten. [B]*There is no answer*[/B] until the final iteration of that LL computation has been completed.

There is a significant error rate in LL testing - any tiny little single-bit glitch at ANY point can create an invalid answer. Thus, the results of LL testing are tested AGAIN by the double-check test - if the results don't match, then one of the test machines had an error, and more doublechecks are done 'till 2 are found that match. It's NOT a good idea to double-check an exponent with the SAME machine that has done a previous check on that same exponent, as that machine is likely to REPEAT the same error.

Finally, if a candidate prime IS found, George or a helper of his with supercomputer access checks that prime again using a different method - testing a SINGLE number to see if it's prime isn't a LOT of work, compared to going through thousands of potential primes....

[QUOTE]Second, *if* the Trial Factoring step does not find a factor, it does a "P-1" and "P-2" step, to look for somewhat larger factors. If it finds a factor in one of those steps, it immediately stops and reports that factor.[/QUOTE]

A little nitpick, there is no P-2 test. All is done is a P-1 test which consists of two stages.

The first stage finds a factor P if all the factors of P-1 are below B1

The second stage finds a factor P if all factors except the largest are below B1 and the largest is below B2