mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2003-09-27, 07:47   #1
mdjvz
 

5·7·113 Posts
Default 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?
  Reply With Quote
Old 2003-09-27, 09:42   #2
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

100101001012 Posts
Default Re: why not stop when composite is prove?

Quote:
Originally posted by mdjvz
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?
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 http://www.mersenne.org/math.htm
smh is offline   Reply With Quote
Old 2003-09-27, 10:44   #3
GP2
 
GP2's Avatar
 
Sep 2003

2·1,291 Posts
Default Re: why not stop when composite is prove?

Quote:
Originally posted by mdjvz
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!
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.
GP2 is offline   Reply With Quote
Old 2003-09-28, 02:15   #4
QuintLeo
 
QuintLeo's Avatar
 
Oct 2002
Lost in the hills of Iowa

26·7 Posts
Default Re: why not stop when composite is prove?

Quote:
Originally posted by mdjvz
Why does the prime95 program has to complete the full 100% checking when it finds BEFORE that the mersenne Number is Composite?
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. *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 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....
QuintLeo is offline   Reply With Quote
Old 2003-09-28, 17:13   #5
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Default

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.
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
smh is offline   Reply With Quote
Reply

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 2018-01-02 11:11
I have to prove everything PawnProver44 Miscellaneous Math 40 2016-03-19 07:33
I take a known prime and prove it to be a composite (..or maybe need help?) storflyt32 storflyt32 112 2015-01-09 04:19
How can I prove this PRP prime? siegert81 Math 2 2014-11-19 10:24
Is this to prove/already known? MatWur-S530113 Math 4 2007-06-27 05:35

All times are UTC. The time now is 03:46.

Wed Dec 2 03:46:49 UTC 2020 up 83 days, 57 mins, 1 user, load averages: 1.82, 1.52, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.