mersenneforum.org > Math will searching for factors sometimes be faster than LL test?
 Register FAQ Search Today's Posts Mark Forums Read

 2003-10-16, 00:19 #1 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 44168 Posts will searching for factors sometimes be faster than LL test? I know that sometimes testing numbers like M 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?
 2003-10-16, 01:29 #2 cheesehead     "Richard B. Woods" Aug 2002 Wisconsin USA 160248 Posts Yes. Putting a certain amount of effort into trying to factor a Mersenne number, before running the L-L 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 trial-factored and how high the limits have been tried for P-1 factoring that Mnumber. Mnumbers for which a factor is found are removed from the list of those eligible for L-L testing (first-time or double-check) assignment. PrimeNet factoring assignments are for trial-factoring Mnumbers before they're assigned for L-L testing. Tradeoff limits are calculated for trial factoring and P-1 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 L-L testing. Below that limit, time spent trying to find a factor is more valuable than time spent L-L 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 L-L testing, Prime95 checks whether it has had P-1 factoring attempted on it, and if not then Prime95 performs P-1 factoring up to the tradeoff limit before starting the L-L test. BTW, only Mnumbers with prime exponents are assigned by GIMPS for factoring and L-L testing, because it is known that all Mnumbers with composite expoments must have proper factors and thus cannot be prime themselves.
2003-10-16, 02:34   #3
Maybeso

Aug 2002
Portland, OR USA

1000100102 Posts

Quote:
 I know that sometimes testing numbers like M takes years.
There are also organized efforts to factor mersennes with composite exponents. These numbers often yield factors more quickly than prime exponents of similar size.

Having said that -- E.Mayer and others have logged very impressive factor lists of mersenne numbers with both prime and composite exponents. They have fine-tuned the process to an amazing level of efficiency - so that whatever catagory of target they focus on usually falls quickly.

2003-10-16, 22:15   #4
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

1BF616 Posts
Re: will searching for factors sometimes be faster than LL test?

Quote:
 I know that sometimes testing numbers like M takes years.
You meant eons - not years, right?

 Similar Threads Thread Thread Starter Forum Replies Last Post boldi Miscellaneous Math 74 2014-04-17 07:16 __HRB__ Information & Answers 6 2009-10-04 19:37 lidocorc Software 3 2008-12-03 15:12 flosculus Information & Answers 6 2008-11-10 18:59 T.Rex Math 0 2004-10-26 21:37

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

Thu Nov 26 03:58:21 UTC 2020 up 77 days, 1:09, 3 users, load averages: 0.99, 1.33, 1.38