Mersenne Digest Tuesday, May 1 2001 Volume 01 : Number 845 ---------------------------------------------------------------------- Date: Sat, 28 Apr 2001 17:18:14 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Mersenne Digest V1 #843 On 28 Apr 2001, at 0:57, [EMAIL PROTECTED] wrote: > > Question (deep) - if we did discover a factor of 2^(2^727-1)-1, > > would that help us to find a factor of 2^727-1 ? The reason for asking this question was twofold: firstly, to find out whether it _might_ be possible to know a factor of 2^c-1 without knowing a factor of c, and secondly, if this statement is not true, (in other words, if finding a factor of M(M(p)) automatically leads to the derivation of a factor of M(p)) to possibly find a factor of the recalcitrant number M(727) by attempting to factor M(M(727)), which probably hasn't had much effort expended on it. Yet. > > I am skeptical too. Show us how the factors > > 131009 of M_(M11) = 2^(2^11 - 1) - 1 > 724639 of M_(M11) > 285212639 of M_(M23) > > lead to factorizations of M11 and M23. Why don't the factors > > 231733529 of M_(M17) > 62914441 of M_(M19) > > lead to similar factorizations of M17 and M19? The "obvious" answer here is that 11 and 23 are "3 mod 4" Sophie Germain primes, whereas neither 17 nor 19 are. I tinkered around a bit with the algebra but wasn't able to come up with a formal justification for this distinction. The point of course is that there is a formal proof that, if a prime p is congruent to 3 modulo 4 and 2p+1 is also prime, then 2^p-1 is divisible by 2p+1 - which makes searching for a factor of M(p) by trying to factor M(M(p)) somewhat pointless! > > With c = 2^727 - 1, 2^751 - 1, 2^809 - 1, 2^997 - 1, 2^1051 - 1, I > looked for factors 2*k*c + 1 of 2^c - 1, but found none with k <= > 20000. I invite those with a special search program for M_(M127) > factors to search these further. None of 727, 751, 809, 997 & 1051 are "3 mod 4" S-G primes (else they wouldn't be on the "factors wanted" lists!) Regards Brian Beesley 1775*2^332181+1 is prime! (100000 digits) Discovered 22-Apr-2001 _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 29 Apr 2001 09:33:24 +0200 (MET DST) From: [EMAIL PROTECTED] Subject: Re: Mersenne: Re: Mersenne Digest V1 #843 "Brian J. Beesley" <[EMAIL PROTECTED]> wrote, in response to my earlier message > The point of course is that there is a formal proof that, if a prime > p is congruent to 3 modulo 4 and 2p+1 is also prime, then 2^p-1 is > divisible by 2p+1 - which makes searching for a factor of M(p) by > trying to factor M(M(p)) somewhat pointless! > > > > With c = 2^727 - 1, 2^751 - 1, 2^809 - 1, 2^997 - 1, 2^1051 - 1, I > > looked for factors 2*k*c + 1 of 2^c - 1, but found none with k <= > > 20000. I invite those with a special search program for M_(M127) > > factors to search these further. > > None of 727, 751, 809, 997 & 1051 are "3 mod 4" S-G primes (else they > wouldn't be on the "factors wanted" lists!) Then I challenge readers to show how to discover the factor 11447 of 2^97 - 1 given the factor 1800*(2^97 - 1) + 1 of M(M97) 97 is not 3 mod 4. Let c be a large positive integer. Given k with 1 <= k <= 20000, the chance that 2*k*c + 1 is a prime divisor of 2^c - 1 is about (1/(2*k)) * (2/ln(2*k*c)) = 1/(k * ln(2*k*c)) Integrate this from k = 1 to k = 20000. An antiderivative is ln(ln(2*k*c)). The integral is ln(ln(40000*c)) - ln(ln(2*c)) = ln( ln(40000*c) / ln(2*c) ) = ln(1 + ln(20000) / ln(2*c) ) For c as large as 10^8, the quotient ln(20000) / ln(2*c) exceeds 0.5, giving an estimated ln(1.5) ~= 0.4 factors with 1 <= k <= 20000. For c = 2^e - 1 with large e, we estimate 14.2/(e + 1) factors with k in this range. This is only 0.02 factors when e = 727, so it should not be surprising that my search was unsuccessful. Extending the search to k < 10^8 will approximately double our chance of success. Peter Montgomery [EMAIL PROTECTED] - --JAA22954.988529496/hera.cwi.nl-- _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 1 May 2001 07:55:51 -0500 From: fay aron charles <[EMAIL PROTECTED]> Subject: Mersenne: Countdown is slowing I've been following the status of gimps recently with the following page: http://mersenne.org/status.htm It shows that the countdown to testing all exponents below M(6972593) at least once is 33. I see this a very large milestone. Last week the countdown was 34, and the week before that it was 34. I would assume the slow progress is because the last few exponents are reserved by people with very slow processors who still update with the server at least every 60 days. Has thought been given to this? Could these last few exponents be assigned for double checking now? It would at least satisfy my curiosity. -aron _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #845 ******************************
