mersenneforum.org  

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

Reply
 
Thread Tools
Old 2003-10-16, 00:19   #1
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

44168 Posts
Default 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?
ixfd64 is offline   Reply With Quote
Old 2003-10-16, 01:29   #2
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

160248 Posts
Default

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.
cheesehead is offline   Reply With Quote
Old 2003-10-16, 02:34   #3
Maybeso
 
Maybeso's Avatar
 
Aug 2002
Portland, OR USA

1000100102 Posts
Default

Quote:
I know that sometimes testing numbers like M<insert 15 digit prime here> 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.
Maybeso is offline   Reply With Quote
Old 2003-10-16, 22:15   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

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

Quote:
I know that sometimes testing numbers like M<insert 15 digit prime here> takes years.
You meant eons - not years, right?
Prime95 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A (new) old, (faster) slower mersenne-(primality) PRP test boldi Miscellaneous Math 74 2014-04-17 07:16
Faster LL-test Bounty Questions __HRB__ Information & Answers 6 2009-10-04 19:37
Double check LL test faster than first run test lidocorc Software 3 2008-12-03 15:12
to be faster at searching mersenne primes flosculus Information & Answers 6 2008-11-10 18:59
A primality test for Fermat numbers faster than P├ępin's test ? 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

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.