Mersenne Digest Monday, July 24 2000 Volume 01 : Number 761 ---------------------------------------------------------------------- Date: Sat, 22 Jul 2000 06:41:16 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Mersenne: Fluke? Hi guys, I found the following in my results.txt file: [Sat Jul 22 01:50:43 2000] P-1 found a factor in stage #2, B1=1000000, B2=25000000. UID: beejaybee/Simon2, M131437 has a factor: 603794102057268841 The interesting thing here is that the prime factorization of P-1 (603794102057268840) is 2^3.3^2.5.57.131437.344879201 i.e. the largest prime factor of P-1 is greater than B2 and I'm therefore unable to understand why P-1 managed to find the factor. Could someone please enlighten me? BTW the factor found is indeed a proper factor of M141437. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Sat, 22 Jul 2000 12:53:30 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Credit for factors found using P-1 tests On 21 Jul 00, at 19:45, Terry S. Arnold wrote: > I don't appear to have gotten credit for a factor found with P-1. > > What is the procedure for getting credit for a factor found during P-1 > testing as part of Double checking? AFAIK PrimeNet doesn't yet have the capability to credit CPU time for P-1 work (although factors found are certainly logged!) The point is that running P-1 is cost effective because by running P-1 with the suggested limits you expect (statistically) to find more factors than you would complete LL tests (first test or DC assignments) in the same time. IMHO PrimeNet _should_ give CPU credit for P-1 tests - in a seperate category like the CPU credit given for factoring assignments. The algorithm would be quite straightforward as there are only two cases to consider: only Stage 1 completed, or Stage 2 completed (whether or not a factor is found - the time is the same!) Implementing this arrangement would also prevent P-1 being run unneccessarily when an assignment is recycled or becomes available for double-checking, and would enable interested people (perhaps with limited CPU power but with adequate memory) to run just P-1 in a coordinated manner. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Sat, 22 Jul 2000 14:01:00 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Fluke? Hi Brian, At 06:41 AM 7/22/00 +0000, Brian J. Beesley wrote: >Hi guys, > >I found the following in my results.txt file: > >[Sat Jul 22 01:50:43 2000] >P-1 found a factor in stage #2, B1=1000000, B2=25000000. >UID: beejaybee/Simon2, M131437 has a factor: 603794102057268841 > >The interesting thing here is that the prime factorization of P-1 >(603794102057268840) is 2^3.3^2.5.57.131437.344879201 i.e. the >largest prime factor of P-1 is greater than B2 and I'm therefore >unable to understand why P-1 managed to find the factor. > >Could someone please enlighten me? If there is enough memory available (and there often is when running P-1 on "small" Mersenne numbers), then prime95 uses Suyama's improvement for stage 2. Paul Zimmermann introduced me to this. I've excerpted his email below. In practice, it is rare that this improvement finds a factor that an ordinary stage 2 would miss. Regards, George you were looking for improvements in phase 2. Here is one which improves the efficiency of phase 2, with about the same memory and time used. It is a slight modification of the birthday paradox continuation improvement suggested by Suyama [see section 3.3 from Richard's paper]. Currently our phase 2 computes some points tQ and sQ (where Q is the point computed at the end of phase 1), and tries all combinations x_t-x_s for t-s<=B2 and prime. Now, for each s and t, compute t^eQ and s^eQ instead for some small integer e, and try all combinations x_{t^e}-x_{s^e} for t-s<=B2 and prime. The overhead will be the computation of t^eQ and s^eQ from tQ and sQ, i.e. about 2*e*sqrt(B2) multiplications of points by a O(B2) scalar. Compared to phase 1 which performs O(B1/log(B1)) multiplications of points by a O(B1) scalar, the overhead remains small when 20*e*log(B1) is small wrt sqrt(B1). The advantage is that now phase 2 will succeed not only if the largest factor of the group order is of the form t-s, but whenever it divides t^e-s^e for some t,s. This improves the number of possibilities, especially when t^e-s^e has many factors: >> Factor(t^48-s^48); 2 2 4 4 8 8 2 2 - - (s + t) (s - t) (s + t ) (s + t ) (s + t ) (s t + s + t ) 2 2 4 4 2 2 8 8 4 4 16 16 8 8 (s - s t + t ) (s + t - s t ) (s + t - s t ) (s + t - s t ) _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Sun, 23 Jul 2000 22:20:52 -0700 From: Gerry Snyder <[EMAIL PROTECTED]> Subject: Mersenne: Should I continue an LL test after h/w problems? A couple of days ago my Win95 machine (Celeron 333) started having problems, the first symptom being sumout != sumin errors in Prime 95 (others started showing up in other s/w soon). After some fiddling around I found that removing one of my RAM DIMMs seemed to restore stability. The LL test on 10402361 is just short of 39% complete, with an expected completion date of 12 Sept. Is it worth the time of letting it complete? BTW, the Pentium 166 machine I use for factoring used to take about 2 days to go up to 2**64, and seemed to average about one factor per month, or a little less. When the limit on the numbers being received went up to 2**65 the time went up to about 10 days. I figured the rate of finding factors would drop to maybe a couple per year or so. But after two Mersenne numbers with no factor up to 2**65, the PC found two in less than hour. Who'd have thunk? Gerry - -- mailto:[EMAIL PROTECTED] Gerry Snyder, AIS Symposium Chair, Region 15 Ass't RVP, JT Chair Member San Fernando Valley, Southern California Iris Societies in warm, winterless Los Angeles _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ Date: Mon, 24 Jul 2000 22:24:45 +0100 From: "Andy" <[EMAIL PROTECTED]> Subject: Mersenne: Assignment of Exponents Just a quick question. Are the lowest exponents assigned first or is it dependent on your CPU power or what? _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt ------------------------------ End of Mersenne Digest V1 #761 ******************************
