Hi, I was thinking about how we could improve the productivity of the project by reducing the proportion of candidates requiring LL testing, and had the following idea.
P-1 factoring is useful when applied to Mersenne numbers because M(p)-1 is easily factored: M(p)-1 = (2^p-1) -1 = 2^p-2 = 2.(2^(p-1)-1) The idea of P-1 factoring (stage 1) is to compute X = 2^k! mod N where k is the B1 limit and N is the number to be factored. Now compute GCD(X-1,N); with luck (if there is a factor F of N for which F-1 is k-smooth) the result will be F rather than 1. However, _for Mersenne numbers_, the principle can be extended as follows: M(p)-M(q) = 2^(p-q).(2^(p-q)-1) Having computed X as above, we can now compute successively GCD(X-1,N) GCD(X-3,N) GCD(X-7,N) ... (until we get bored, or run out of q<p) instead of just GCD(X-1,N). This does not cost a lot of extra time because (for sensible values of k) the GCD will usually run in a small fraction of the time required to compute X. Nevertheless we appear to be gaining a lot of opportunities to find a factor. Q1. What's the problem with this line of argument? I find it hard to believe that something this simple has been missed in the past... Q2. If the above argument _is_ sound, is there an equally straightforward extension to stage 2? Q3. Obviously there is still a falloff point at which it isn't worth proceeding further - some Mersenne numbers are going to remain hard to factor in the sense that any factoring method will take at least as long as running a couple of LL tests. Can anyone figure out how we can make a sane decision as to when it is no longer worth proceeding to the next q in computing GCD(X-M(q),2^p-1) ? Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
