Mersenne Digest Friday, April 7 2000 Volume 01 : Number 715 ---------------------------------------------------------------------- Date: Wed, 5 Apr 2000 17:32:39 EDT From: [EMAIL PROTECTED] Subject: Mersenne: Re: Mersenne Digest V1 #714 _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 05 Apr 2000 16:26:39 +0200 From: Harald Tveit Alvestrand <[EMAIL PROTECTED]> Subject: Mersenne: Windows 2000, batteries and Prime95 FWIW - Prime95 version 19.2.1 running under Windows 2000 knows how to stop when the machine is on battery power. But I'd prefer an "NT service" version - the "Windows95/98 service" option is not available in Prime95. Can anyone tell me if the NT service version will stop when on battery, if running under Windows 2000? Harald (eternal optimist) - -- Harald Tveit Alvestrand, EDB Maxware, Norway [EMAIL PROTECTED] _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Apr 2000 08:45:55 +1200 (NZST) From: Bill Rea <[EMAIL PROTECTED]> Subject: Mersenne: poorly factored exponents Gimpsters, I went to check out a new exponent from the manual testing pages for first time LL testing and discovered a batch of poorly factored exponents on offer. Just recently I'd picked up my first exponents above 10,000,000, but these were around the 9.9M and had only been factored to 55-bits. All the other exponents I have out have been factored to 64-bits. I tried checking out several hoping to get one that had been factored deeper, but after checking out four which had been factored to 55 bits, I stopped and checked them back in again. As I'm running Ernst Mayer's Mlucas I haven't got any way to factor these. If any wants to look for them the ones I picked up were:- 9987931 9987979 9988109 9988157 I'll need a new exponent in about 10 hours so I'll be trying again soon. Bill Rea, Information Technology Services, University of Canterbury \_ E-Mail b dot rea at its dot canterbury dot ac dot nz </ New Phone 64-3-364-2331, Fax 64-3-364-2332 /) Zealand Unix Systems Administrator (/' _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 06 Apr 2000 20:48:23 EDT From: "Nathan Russell" <[EMAIL PROTECTED]> Subject: Re: Mersenne: poorly factored exponents >From: Bill Rea <[EMAIL PROTECTED]> >Reply-To: Bill Rea <[EMAIL PROTECTED]> >To: [EMAIL PROTECTED] >Subject: Mersenne: poorly factored exponents >Date: Fri, 07 Apr 2000 08:45:55 +1200 (NZST) > >Gimpsters, > >I went to check out a new exponent from the manual testing pages for >first time LL testing and discovered a batch of poorly factored >exponents on offer. Just recently I'd picked up my first exponents >above 10,000,000, but these were around the 9.9M and had only been >factored to 55-bits. All the other exponents I have out have been >factored to 64-bits. I tried checking out several hoping to get one >that had been factored deeper, but after checking out four which had >been factored to 55 bits, I stopped and checked them back in again. As >I'm running Ernst Mayer's Mlucas I haven't got any way to factor >these. > > >If any wants to look for them the ones I picked up were:- > > 9987931 > 9987979 > 9988109 > 9988157 > > >I'll need a new exponent in about 10 hours so I'll be trying again >soon. > > >Bill Rea, Information Technology Services, University of Canterbury These exponents originate from a user that has been doing factoring to small depths on several hundred, if not thousand, exponents. Check the list archives from about 2 weeks ago. The factoring machines should have the majority of these taken care of in a month or so. Does anyone have a solution? Until one is found, I would suggest contacting George to get assignments that have been factored deeper ([EMAIL PROTECTED]), or using the machine for double-checking for a little while. I don't know if PrimeNet will allow another user to factor exponents that have been checked out to you and nevertheless accept the LL results from you without you having run factoring. Maybe Scott or one of the other PrimeNet people could answer this for you. BTW, I'm a relative newbie here, and any/all of the info I have given you may be incorrect. Regards, Nathan Russell ______________________________________________________ Get Your Private, Free Email at http://www.hotmail.com _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Apr 2000 07:15:57 +0200 From: Martijn Kruithof <[EMAIL PROTECTED]> Subject: Mersenne: V20 Hi, A small suggestion for the V20 is also to output the P-1 factoring progress information once in a while to the results file. I have currently 3 cpu's doing P-1 factoring, and I do not see anything at all in the results file. Furthermore the machines busy P-1 factoring do not update anything on the primenet server. (unless I switch back to the nt V19 service version when booting windows on two of them) Kind Regards, Martijn _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 7 Apr 2000 06:26:24 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: poorly factored exponents On 6 Apr 00, at 20:48, Nathan Russell wrote: > These exponents originate from a user that has been doing factoring to > small depths on several hundred, if not thousand, exponents. Check the > list archives from about 2 weeks ago. Actually PrimeNet should take care of that problem itself. There always have been, for some reason, some exponents which get assigned as LL tests or even double checks which are factored short. George's programs simply do the required factoring before going on to the LL test - unless a factor is found 8-) > Does anyone have a solution? Until one is found, I would suggest > contacting George to get assignments that have been factored deeper > ([EMAIL PROTECTED]), or using the machine for double-checking for a > little while. Or try picking up exponents shortly after 0600 GMT for reasons which have been explained previously. > I don't know if PrimeNet will allow another user to factor > exponents that have been checked out to you and nevertheless accept the LL > results from you without you having run factoring. Maybe Scott or one of > the other PrimeNet people could answer this for you. If I take an assignment from PrimeNet, there's nothing to stop me subcontracting any trial factoring to a third party. The third party probably won't get credit for the factoring work done, but neither will I. However, most people in Bill Rea's position will be able to find a PC lying around somewhere & should be able to do the factoring work on that. A PC well short of the current state of the art should be able to do trial factoring fast enough to keep a Sun E450 system running Mlucas supplied with prefactored LL assignments, without having to work more than one day a week! There are also factoring programs available in portable high-level- language source format, in particular look for Mfactor.c If it wasn't for the fact that factoring is so far ahead of LL testing, I'd probably switch my Alpha system to factoring - with its 64 bit integer registers and quad-issue pipeline, the architecture is much better suited to factoring than LL testing, and the performance is somewhat startling for factoring (up to 63 bits) even though the program is neither tuned to the hardware nor hand optimized. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 7 Apr 2000 06:26:24 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: V20 On 7 Apr 00, at 7:15, Martijn Kruithof wrote: > A small suggestion for the V20 is also to output the P-1 factoring > progress information once in a while to the results file. I have > currently 3 cpu's doing P-1 factoring, and I do not see anything > at all in the results file. Writes to the results file at the end of Stage 2 even if no factor is found. This is the same strategy as for trial factoring, which take a similar time to complete. Furthermore the machines busy P-1 > factoring do not update anything on the primenet server. (unless > I switch back to the nt V19 service version when booting windows > on two of them) The PrimeNet server can't do anything with P-1 at the moment except to log any factors found. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 7 Apr 2000 09:40:51 -0700 From: Paul Leyland <[EMAIL PROTECTED]> Subject: Mersenne: P-1 factoring of large exponent Mersenne numbers A nasty thought just struck me. It's well known that factors of M(p) are of the form 2kp+1. It's also well known that factors found by the P-1 algorithm are of the form (product of powers of small primes) + 1 where "small" means less than an arbitrarily chosen limit B1. I omit stage 2 from consideration here. When applying P-1 to mersenne numbers, an additional 2*p ought to be included in the product, over and above all the powers of prime < B1. Can anyone who knows for certain reassure me that this has been done for the prime95 V20 implementation? If it hasn't been done, my computation for the QA effort on M(42282367) with B1 = 1000000 has been a waste of a week's cpu. Paul _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 7 Apr 2000 10:35:14 -0700 From: Will Edgington <[EMAIL PROTECTED]> Subject: Mersenne: P-1 factoring of large exponent Mersenne numbers Paul Leyland writes: A nasty thought just struck me. It struck me in a different context some time ago; it might even be archived. When applying P-1 to mersenne numbers, an additional 2*p ought to be included in the product, over and above all the powers of prime < B1. Can anyone who knows for certain reassure me that this has been done for the prime95 V20 implementation? I don't know about the prime95 V20 implementation per se, but George was aware of this quite some time ago, because he once told me that it is/was being done in Factor98, his older, stand-alone, P-1 factorer. While I'm here, I still accept P-1 factoring reservations and Factor98 and Factor95 save files for small exponent Mersennes. Will _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Apr 2000 13:59:42 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Re: Mersenne: V20 Hi Martijn, At 07:15 AM 4/7/00 +0200, Martijn Kruithof wrote: >A small suggestion for the V20 is also to output the P-1 factoring >progress information once in a while to the results file. OK. The next version will work the same way LL testing and factoring does. It will use the "Iterations between results file outputs" preference. It will also output when you stop mprime. >Furthermore the machines busy P-1 >factoring do not update anything on the primenet server. Your statement could mean two things: 1) Your prime.spl file is not getting sent to the server. A possible bug in this regard is fixed in the next beta. Stopping and starting the current beta should send the spool file. 2) Your P-1 progress is not getting sent to the server. This won't happen until version 21. Regards, George _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Apr 2000 14:15:24 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Re: Mersenne: P-1 factoring of large exponent Mersenne numbers Hi Paul, At 09:40 AM 4/7/00 -0700, Paul Leyland wrote: >When applying P-1 to mersenne numbers, an additional 2*p ought to be >included in the product, over and above all the powers of prime < B1. Can >anyone who knows for certain reassure me that this has been done for the >prime95 V20 implementation? This has been done. Your CPU-week has not been wasted. Regards, George _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 07 Apr 2000 14:21:04 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Windows 2000, batteries and Prime95 Hi, At 04:26 PM 4/5/00 +0200, Harald Tveit Alvestrand wrote: >FWIW - Prime95 version 19.2.1 running under Windows 2000 knows how to stop >when >the machine is on battery power. > >Can anyone tell me if the NT service version will stop when on battery, if >running under Windows 2000? The stop when on battery feature is not implemented in the NT service version. Sorry, George _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 7 Apr 2000 20:42:51 +0000 From: Alexander Kruppa <[EMAIL PROTECTED]> Subject: Re: Mersenne: P-1 factoring of large exponent Mersenne numbers Paul Leyland wrote: > It's well known that factors of M(p) are of the form 2kp+1. > > When applying P-1 to mersenne numbers, an additional 2*p ought to be > included in the product, over and above all the powers of prime < B1. Can > anyone who knows for certain reassure me that this has been done for the > prime95 V20 implementation? Yes, thats a property of P-1 that makes it very well-suited for factoring Mersennes. If the exponent is 10^x, you get x (+log_10(2) to be precise..) digits in the factor for free. This is used in all P-1 implementations that I am aware of. And here's another little extra: Factors are 1 or 7 (mod 8). Lets look at the 1 (mod 8) case: 2kp+1 = 1 (8) 2kp=0 (8) kp=0 (4) p is an odd prime => k is divisible by 4. Since the chance of the factor being 1 (8) seems to be 50%, 4 has a 50% chance of dividing k, 8 has a 25% chance, etc, so on average, theres yet another 2! So you best start by exponentiating your root by 4*p. Considering the 7 (mod 8) case (I dont know the proof off my head) it turns out that 3 has a 50% chance of dividing k, 5 has a 25% chance, 7 a 1/6 chance etc - so the k is a little more smooth then you'd expect a random number to be. I've been stuggling with modelling this into a formula that tells the chance of finding a factor of a given size with P-1, given certain bounds, but I got lost in cases that mutually exclude somewhere.. I have a little time now (exams done! :) and try some more. Somehow I feel that, since the 1 or 7 (8) property halves the number of factors to consider and P-1 seems to fully benefit from this property through "extra smoothness", the difficulty of the task of factoring k by P-1 should be reduced to factoring some number k/sqrt(2). That would be interesting to (dis-)prove. Ciao, Alex. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 7 Apr 2000 23:05:00 +0200 From: "Martijn Kruithof" <[EMAIL PROTECTED]> Subject: Re: Mersenne: V20 Hi, Thanks for the info and the change of writing the result file, it is my only source for progress information, and it is nice if at least approx once a day / every two days some progress is reported. I meant statement 1 regarding the updating on the server. Kind Regards, Martijn > Hi Martijn, > > At 07:15 AM 4/7/00 +0200, Martijn Kruithof wrote: > >A small suggestion for the V20 is also to output the P-1 factoring > >progress information once in a while to the results file. > > OK. The next version will work the same way LL testing and factoring > does. It will use the "Iterations between results file outputs" preference. > It will also output when you stop mprime. > > >Furthermore the machines busy P-1 > >factoring do not update anything on the primenet server. > > Your statement could mean two things: > 1) Your prime.spl file is not getting sent to the server. A possible bug > in this regard is fixed in the next beta. Stopping and starting the > current beta should send the spool file. > 2) Your P-1 progress is not getting sent to the server. This won't happen > until version 21. > > Regards, > George > > _________________________________________________________________ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers > _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 7 Apr 2000 15:06:55 -0700 From: Russel Brooks <[EMAIL PROTECTED]> Subject: Mersenne: Broke into top 2000 I just met a personal GIMPS objective; I just broke into the top 2000 (I'm #1993 at the moment). I only started last fall. The last couple of jumps up the ladder have been getting smaller and smaller so I'm not confident of ever making the top 1000. Cheers... Russ aka:"rlbrooks" _________________________________________________________________ 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 #715 ******************************
