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)
Ok, lets establish variable names: p, q and f are primes. f|N, N is the number to be factored X = a^E, a is the P-1 base, E is the P-1 exponent (E=k! is your example) P-1 algo: gcd(a^E-1, N) Your variation suggests gcd(a^E-d, N), where d = M(q). The factorization of N-1 is not directly related to the factorization of N. Two ways in which they are connected are that N and N-1 have no factors in common, and that if N +/- 1 one is a perfect power, then we know something of the form of the factors f, i.e. if N=2^p-1 and f|N, then p|f-1. However, the fact that N +/- 1 is easily factored (i.e. because is it a perfect power) does not imply an extremely efficient factoring method for N. (Well, it does: SNFS. But that's irrelevant for the numbers we want to test for primality). The reason that P-1 is nice for Mersennes and other perfect powers +/- 1 (N=a^k+/-1) is that (in the primitive part of N) all factors f have k|f-1. If k is of the order of 10^7, you're getting 7 digits of the factor "for free" by including k in E. > 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. In the case of Mersenne numbers, 2 is not a good choice for the base. By Knuth's GCD lemma, gcd(2^n-1, 2^m-1) = 2^gcd(n, m) - 1. In the case of N=M(p), one will find a "factor" iff p|E, and then the "factor" will be trivial, namely M(p) itself. Using k! for the P-1 exponent will work, but is not very efficient. It will greatly overrepresent small primes. The product of primes and prime powers <B1 is normally used. > However, _for Mersenne numbers_, the principle can be extended as follows: > > M(p)-M(q) = 2^(p-q).(2^(p-q)-1) I think you meant (2^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). Now, X is not itself a Mersenne number. It is, with luck, something that is 1 (mod f) where f|M(p). So whether or not M(p)-M(q) has many small factors is not really relevant here. Even if X was a Mersenne number M(n), M(n)-M(q) = 2^q * M(n-q), then GCD(2^p * M(n-q), M(p)) = 1 or M(p), giving only trivial factorizations. The P-1 method works because a^(f-1) == 1 (mod f), by Fermat's Little Theorem. If one exponentiates by some multiple of f-1, i.e. n(f-1) the result is still 1, as a^(n(f-1)) = (a^(f-1))^n == (1)^n == 1 (mod f). If one keeps exponentiating, the residue (mod f) will become 1 at some point and be "stuck" there. If one subtracts 1 now, one gets something that is 0 (mod f) and thus a multiple of f, so that f appears in the gcd with N. Subtracting d != 1 will only make sense if there is reason to believe that X == d (mod f). Since X=a^E and E contains small primes and prime powers, X will have an order (mod f) that is the order of a but with small primes removed, ord(X) = ord(a)/gcd(ord(a),E). If the order of a (mod f) had only small primes to begin with, the order of X will be 1 and thus X == 1 (mod f). Otherwise, the order of X will be a prime or product of primes >B1. What the residue class of such an X is (mod f) is impossible to guess without knowing f, that means we cannot figure out which d to subtract to make X-d == 0 (mod f). The chance of hitting the correct d by random choice is 1/f, as far as I can see d=M(q) has no better or worse chance than a random choice. Alex _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
