20031016, 00:19  #1 
Bemusing Prompter
"Danny"
Dec 2002
California
3×829 Posts 
will searching for factors sometimes be faster than LL test?
I know that sometimes testing numbers like M<insert 15 digit prime here> takes years. Yet, some people like Ernst Mayer (Ewmayer) have been able to find factors within minutes. Would this be useful in filtering out exponents know to yield composite numbers?

20031016, 01:29  #2 
"Richard B. Woods"
Aug 2002
Wisconsin USA
17014_{8} Posts 
Yes. Putting a certain amount of effort into trying to factor a Mersenne number, before running the LL test on that number, has always been a part of GIMPS. The GIMPS database keeps a record of how far each Mnumber with a prime exponent has been trialfactored and how high the limits have been tried for P1 factoring that Mnumber.
Mnumbers for which a factor is found are removed from the list of those eligible for LL testing (firsttime or doublecheck) assignment. PrimeNet factoring assignments are for trialfactoring Mnumbers before they're assigned for LL testing. Tradeoff limits are calculated for trial factoring and P1 factoring. Tradeoff limits are the limits at which (the time spent factoring) divided by (the probability of finding a factor) equals the time required for LL testing. Below that limit, time spent trying to find a factor is more valuable than time spent LL testing. Then when a Mnumber is assigned for trial factoring, Prime95 performs as much trial factoring as is required to go up to the tradeoff limit. When a Mnumber is assigned for LL testing, Prime95 checks whether it has had P1 factoring attempted on it, and if not then Prime95 performs P1 factoring up to the tradeoff limit before starting the LL test. BTW, only Mnumbers with prime exponents are assigned by GIMPS for factoring and LL testing, because it is known that all Mnumbers with composite expoments must have proper factors and thus cannot be prime themselves. 
20031016, 02:34  #3  
Aug 2002
Portland, OR USA
100010010_{2} Posts 
Quote:
Having said that  E.Mayer and others have logged very impressive factor lists of mersenne numbers with both prime and composite exponents. They have finetuned the process to an amazing level of efficiency  so that whatever catagory of target they focus on usually falls quickly. 

20031016, 22:15  #4  
P90 years forever!
Aug 2002
Yeehaw, FL
2^{2}·43·47 Posts 
Re: will searching for factors sometimes be faster than LL test?
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
A (new) old, (faster) slower mersenne(primality) PRP test  boldi  Miscellaneous Math  74  20140417 07:16 
Faster LLtest Bounty Questions  __HRB__  Information & Answers  6  20091004 19:37 
Double check LL test faster than first run test  lidocorc  Software  3  20081203 15:12 
to be faster at searching mersenne primes  flosculus  Information & Answers  6  20081110 18:59 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 