Hi all, I think I found a (although purely theoretical) way to find a factor of M(p) by factoring M(M(p)). Ok here goes: f is a prime factor of M(M(p)), 2^(M(p)) = 1 (mod f) so the order of 2 in Z/f*Z is !=1, divides M(p) but is not neccessarily equal to M(p). Lets call it c. Since the order of 2 also divides f-1, c|f-1. The problem with trial division of M(M(p)) is that you can't limit the candidate divisors to multiples of the factors of M(p) when you know these factors - so you'd have to resort to testing all primes as candidate divisors (or at least those where divisor-1 has a large prime factor). This is impractical for large c and therefore large f. The interesting case is when c != M(p), f != 1 (mod M(p)) and f = 2*k*c+1 for a small k. Then the P-1 method could recover that factor if the bound is >=k or k is smooth and you do an extra exponentiation by M(p), i.e. f = GCD(3^(M(p)*E)-1,M(M(P))), E product of primes and prime powers <=bound. The trick here is that P-1 finds the factor f if the exponent E is any multiple of f-1. You don't have to know c in order to exponentiate by it - knowing that c|M(p) suffices. GCD(M(p), f-1) will finally recover the factor of M(p). The only drawback is that M(M(727)), and indeed any M(M(P)) for yet unfactored M(p), is so gargantuan that doing arithmetic modulo it is completely out of the question. But the idea looks interesting on paper. Ciao, Alex. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
