Brian J. Beesley wrote: > 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)
Knowing that there is a factor of 2 does not qualify M(p)-1 as "easy" to be factored. Any sensible factoring program removes all factors below a small bound by trial division which takes no time at all. The "hard" part of factoring is pulling out the large factors that remain. > > 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) M(p) - M(q) = 2^p - 1 - (2^q - 1) = 2^p - 2^q = 2^q (2^(p-q) - 1) Not what you wrote above. And how does this fact relate to anything else? > > 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... Your right, it won't cost a lot of extra time. It also won't accomplish anything. 2^(k!) - 1 has special number theoretic properties that make it highly prone to capturing factors. However, 2^(k!) - 3, and so on, have no such properties, and are basically useless for finding factors. > > 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 > _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
