Will Edgington wrote: > > Is it worthwhile mounting a formal attack on the Mersenne numbers > between 20 million & say 40 million using this technique? We're > getting quite close to this & I think Chris would not have bothered > with these, since they were so far ahead of LL testing at that > point (first tests around 6 million). > > I actually run the program I mention above regularly, but it isn't of > much use in eliminating Mersenne prime candidates because it finds the > factors in factor order rather than in Mersenne exponent order. > Further, virtually all prime numbers are factors of Mersenne numbers > with composite exponents rather than Mersenne numbers with prime > exponents.
My program only test prime p that divide f-1 so it only finds factors of prime exponent Mersennes. But the exponents are mostly very large, not that much smaller than f. Afaik, the chance that a prime of the form 2kp+1 divides M(p) is ~1/k, so the factors f where p is much smaller than f will be rare. The reverse factoring method mostly finds factors of frightingly large Mersenne numbers that are way outside the interval of Mersenne prime candidates of interest to GIMPS. I've made this very rough estimate: My K6-2 500MHz takes 4 minutes to factor a 20M exponent from 2^56 to 2^57. (All exponents in nofactor.txt are factored to at least 2^56) There are ~700000 exponents in nofactor.txt that are factored to 2^56, so the K6 would take < 2.8*10^6 minutes to factor all remaining exponents to 2^57 (this is an overestimate as the larger exponents are faster). I've made some modifications to ismersfac to speed things up (the new version takes 2 seconds for f<10M). It takes 9 minutes for 2^29 < f < 2^30. When testing factors in [2^n, 2^n+1], the time seems to be proportional to about (2^n)^k where k is ~1.35 for n=29 but grows for greater n. Is surely is >1.4 for n=56. So for n=56, ismersfac should take at least (2^27)^1.4 = 2.4*10^11 times as long as for n=29, which is ~10^12 minutes. This estimate is very crude and probably off by orders of magnitude, but rather too low than too high. At any rate it shows that the reverse factoring method is probably not efficient to find larger factors of Mersenne numbers. > Taking all of this into account, I'm fairly certain that the technique > is not - or is at least no longer - useful for GIMPS's purposes. > > Will I agree with Will. Alex _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
