View Single Post
Old 2003-06-22, 14:27   #7
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×599 Posts
Default

Quote:
Originally Posted by jocelynl
take M67 - 1 (2^67-2)
all factors of this are: (2,3,3,7,23,67,89,683,20857,599479)
so it contains 67
and it`s the same for all mersenne.
So, are you saying your method of finding factors of Mersenne numbers requires completely factoring (Mersenne number - 1) in each case?

That task, in general, is not faster than Lucas-Lehmer. Sure, it's cost-effective to use certain amounts of trial factoring, P-1, and ECM to try to find factors of Mersenne numbers before performing the L-L. But for any large Mersenne number, those certain points take us only a small fraction of the way through all possible factors. Beyond those points (which differ according to the particular method), it is faster to prove a Mersenne number composite by L-L than by finding a factor.
cheesehead is offline   Reply With Quote