Geoffrey Reynolds wrote: > For the exponents currently being assigned from primenet > it takes this machine about 12 minutes to factor from > 2^57 to 2^58. > > I thought I would try factoring some small exponents > (under 1,000,000) from the nofactors.zip file. I put > FactorOverride=64 into prime.ini and started mprime as > usual but progress is _much_ slower, it will take about > 8 hours to factor from 2^57 to 2^58. > > Can someone tell me why the time difference is so great?
Any factor of a Mersenne number 2^p-1 (with p an odd prime) must be of the form 2kp+1, whete k is some integer and p is the exponent of 2 in the Mersenne number. If p is small, the potential factors are closer together, and thus there are more of them in a given range (such as between 2^57 and 2^58), than if p were larger. E.g., for 2^19373911-1, the values of 2kp+1 are 38747823, 77495645, 116243467, ..., spaced 38747822 apart. For 2^757-1, the values of 2kp+1 are 1515, 3029, 4543, ..., spaced 1514 apart. In any given interval (such as between 2^57 and 2^58) there are about 26,000 times as many of the 2*k*757+1 candidates as there are of the 2*k*19373911+1 candidates. So trial factoring between 2^57 and 2^58 for 2^757-1 takes about 26,000 times as long as trial factoring the same range of candidate factors for 2^19373911-1. Prime95 trial factoring code uses various sieves to eliminate some of these candidates before actually trying to divide by them, but the proportion thus eliminated is roughly the same regardless of exponent size, so the ratio of trial factoring times remains roughly equal to the inverse ratio of exponents. Richard Woods _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
