20030927, 07:47  #1 
3×919 Posts 
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? 
20030927, 09:42  #2  
"Sander"
Oct 2002
52.345322,5.52471
29·41 Posts 
Re: why not stop when composite is prove?
Quote:
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 http://www.mersenne.org/math.htm 

20030927, 10:44  #3  
Sep 2003
3^{2}·7·41 Posts 
Re: why not stop when composite is prove?
Quote:
Note that TWO fullymatching independent LucasLehmer tests are required for each exponent (unless a factor was found), because the error rate for the result is between 3.54.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. 

20030928, 02:15  #4  
Oct 2002
Lost in the hills of Iowa
2^{6}×7 Posts 
Re: why not stop when composite is prove?
Quote:
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 "P1" and "P2" 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 P1/P2 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. *There is no answer* until the final iteration of that LL computation has been completed. There is a significant error rate in LL testing  any tiny little singlebit glitch at ANY point can create an invalid answer. Thus, the results of LL testing are tested AGAIN by the doublecheck 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 doublecheck 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.... 

20030928, 17:13  #5  
"Sander"
Oct 2002
52.345322,5.52471
29·41 Posts 
Quote:
The first stage finds a factor P if all the factors of P1 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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
So how must we be able to prove the following?  George M  Miscellaneous Math  5  20180102 11:11 
I have to prove everything  PawnProver44  Miscellaneous Math  40  20160319 07:33 
I take a known prime and prove it to be a composite (..or maybe need help?)  storflyt32  storflyt32  112  20150109 04:19 
How can I prove this PRP prime?  siegert81  Math  2  20141119 10:24 
Is this to prove/already known?  MatWurS530113  Math  4  20070627 05:35 