Mersenne Digest Sunday, 26 April 1998 Volume 01 : Number 351 ---------------------------------------------------------------------- From: "John R Pierce" Date: Fri, 24 Apr 1998 09:56:07 -0700 Subject: Re: Mersenne: Lucas-Lehmer test idea >I was wondering whether it is possible to calculate the result of the >Lucas-Lehmer test (of p) modulo another number (q). Ie you calculate L(n+1) >= (Ln -2)^2 mod p mod q. Say (for a moment) this was possible, you would do >the Lucas-Lehmer test using the reduced size arithmetic of q (hence much >quicker than using the large arithmetic of p). At the end you would have >the residue mod q. If it was 0 then you would know that there would be a >good chance (q-1)/q that you had found a prime and that it would be worth >while doing a long test. I might be wrong, but I thought that 'P' was ~ 2^64 in the current Prime95. Pentii class CPUs do 64 bit mul or add in a single cycle (in the form of the mantissa of a FP number). Going to a smaller 'word' wouldn't help much (unless maybe you got down to 16 bit so you could use the 4-at-a-time math of the MMX, but its multiply is somewhat funky). - -jrp ------------------------------ From: "Guillermo Ballester Valor" Date: Sat, 25 Apr 1998 11:37:05 +0200 Subject: Mersenne: Security and *all integer FFT's* Hi to all: There are some people in this group trying to do an *all integer FFT* so fast to be a good option in very big multiplication. I am thinking in the security of these kind of FFT's. In the *real-trigonometric* form there is a good way to see if something is wrong, because all the real elements in the convolution result must be close to an integer. So, if the round-off error is greater than a fixed value, the result is wrong, and we must look for a bug in the program or a hardware error. In the integer form, all the elements in the convolution result are integer. How can we detect an error?. I've found an easy solution, too much easy solution to be new, and likely somebody has thought the same. The cost of the security must be some bits of precision. Let a0, a1,... an and b0, b1,... bn the digits of two big numbers A and B. We want make A*B via an integer FFT. The convolution result is: c0=a0*b0 , c1=(a0*b1+a1*b0)... ck= sum of (ai*bj) where k=i+j if we pre-multiplicate all digits by a small prime (say 7), then *all* the results of the convolution *must* be 0 mod (7*7). Of course, we have to divide again by 49 before normalization. If there is an error in FFT, what is the probability that 49 were divisor of *every* element in convolution? It seems to me is near to zero. Well, sorry if all you already know this. With this method we have to reserve some bits in every digit and and we will lost some efficiency, but I think we need an *almost free of errors* method. We all left our systems running 24 hours a day. How much time we will take to do a LL-test in the 20000000 range?. what happens if there is a bug like oldest Pentium's in the future? Thanks for your time. ************************************** Guillermo Ballester Valor c/ Córdoba, 19 18151-Ogijares (SPAIN) Phone: 34 58 597503 E-mail: gbv@ctv.es ************************************* ------------------------------ From: Peter-Lawrence.Montgomery@cwi.nl Date: Sat, 25 Apr 1998 13:11:22 +0200 (MET DST) Subject: Re: Mersenne: Security and *all integer FFT's* Guillermo Ballester Valor writes: > There are some people in this group trying to do an *all integer FFT* > so fast to be a good option in very big multiplication. > > I am thinking in the security of these kind of FFT's. In the > *real-trigonometric* form there is a good way to see if something is wrong, > because all the real elements in the convolution result must be close to an > integer. So, if the round-off error is greater than a fixed value, the > result is wrong, and we must look for a bug in the program or a hardware > error. > > In the integer form, all the elements in the convolution result are > integer. How can we detect an error?. I've found an easy solution, too much > easy solution to be new, and likely somebody has thought the same. > > The cost of the security must be some bits of precision. Let > > a0, a1,... an and b0, b1,... bn > > the digits of two big numbers A and B. We want make A*B via an integer FFT. > The convolution result is: > > c0=a0*b0 , c1=(a0*b1+a1*b0)... ck= sum of (ai*bj) where k=i+j (suggests pre-multiplying everything by 7 and dividing by 7^2 after the reverse transform) Yes, defensive programming is desirable, to catch hardware and software errors. All LL tests are supposed to be completed twice, using different hardware and software platforms. This should catch many of the errors, and alert us if one program is consistently wrong. Whether we use an integer or real FFT, we have bounds on the inputs ai and bj. This bound is typically the radix used for multiple-precision arithmetic, if we ignore the DWT (Discrete Weighted Transform) modifications. This gives us bounds on the output digits of the convolution. Usually the integer FFT is done modulo a prime (or prime product) larger than this bound. For example, when doing an LL test on M(p) for p near 4 million, we might split a residue into 2^18 = 262144 pieces in radix 2^16. The product coefficients are bounded by 2^18 * (2^16)^2 = 2^50. If we do an integer FFT modulo a 62-bit prime, we have 12 bits of security to catch algorithmic and hardware errors. ------------------------------ From: Nick Craig-Wood Date: Sat, 25 Apr 1998 16:34:08 +0100 (BST) Subject: Re: Mersenne: Security and *all integer FFT's* Peter-Lawrence.Montgomery@cwi.nl wrote: > For example, when doing an LL test on M(p) for p near 4 million, > we might split a residue into 2^18 = 262144 pieces in radix 2^16. > The product coefficients are bounded by 2^18 * (2^16)^2 = 2^50. > If we do an integer FFT modulo a 62-bit prime, we have 12 bits > of security to catch algorithmic and hardware errors. These "security" bits are all at the top of the number though. By using the premultiplication method you will get some bits at the bottom of the number which will probably catch more errors or at least errors of a different type. - -- Nick Craig-Wood ncw1@axis.demon.co.uk http://www.axis.demon.co.uk/ ------------------------------ From: Nick Craig-Wood Date: Sat, 25 Apr 1998 22:30:41 +0100 (BST) Subject: Re: Mersenne: Lucas-Lehmer test idea John R Pierce wrote: > Nick Craig-Wood wrote: > > > I was wondering whether it is possible to calculate the result of the > > Lucas-Lehmer test (of p) modulo another number (q). I should have said q << p here! Ie q is 64 bits where p is 4 million... > > Ie you calculate L(n+1) = (Ln -2)^2 mod p mod q. Say (for a moment) > > this was possible, you would do the Lucas-Lehmer test using the reduced > > size arithmetic of q (hence much quicker than using the large arithmetic > > of p). At the end you would have the residue mod q. If it was 0 then > > you would know that there would be a good chance (q-1)/q that you had > > found a prime and that it would be worth while doing a long test. > > I might be wrong, but I thought that 'P' was ~ 2^64 in the current > Prime95. If you request an exponent from the internet prime server at the moment it will be about 2^22 ie 4 million bits or so. This is around one million decimal digits! The reason that the Lucas-Lehmer test takes so long is that you have to do 2^22 squarings on 2^22 bit numbers - an awful lot of operations - in order to prove a number prime. I was trying to think of a method which would give you a probable mersenne prime much quicker that the complete primality test. If you found a probable prime you would do the full test to make sure. - -- Nick Craig-Wood ncw1@axis.demon.co.uk http://www.axis.demon.co.uk/ ------------------------------ From: Will Edgington Date: Sat, 25 Apr 1998 14:43:11 -0700 Subject: Mersenne: Progress report The new first factor counts, and the increases since my March 14th report, are: 37 Mersenne primes, none new, from 2 to 3021377. 141 completely factored exponents, three new, from 11 to 32531. 64798 first factors from 2 to 1345000 (15 new, 3 now completely factored) 14174 first factors from 1345000 to 1675000 (none new) 13794 first factors from 1675000 to 2000000 (none new) 13841 first factors from 2000000 to 2330000 (none new) 13361 first factors from 2330000 to 2655000 (none new) 26873 first factors from 2655000 to 3310000 (17 new) 26231 first factors from 3310000 to 3960000 (173 new) 25588 first factors from 3960000 to 4605000 (208 new) 25859 first factors from 4605000 to 5260000 (120 new) 46256 first factors from 5260000 to 6540000 (unknown) 43645 first factors from 6540000 to 7820000 (unknown) 42604 first factors from 7820000 to 9090000 (unknown) 42479 first factors from 9090000 to 10380000 (unknown) 78104 first factors from 10380000 to 12895000 (unknown but large) 75009 first factors from 12895000 to 15400000 (unknown but large) 39028 first factors from 15400000 to 16777216 (unknown but large) 33169 first factors from 16777216 to 17945000 (unknown but large) 71559 first factors from 17945000 to 20500000 (unknown but large) 55793 first factors from 20500000 to 30000000 (21321 new) 28102 first factors from 30000000 to 41000000 (none new) 61095 first factors from 41000000 to 60000000 (none new) 47857 first factors from 60000000 to 82000000 (none new) 121934 first factors from 82000000 up (2 new) The 'unknown's are because the ranges that I reported last time were not matched to George's FFT length ranges; the ranges above are matched to George's thru 20.5 million. The 'but large's and the 21,321 just after them are from the trial factoring that Jean-Charles Meyrignac, George Woltman, and I did on large numbers of exponents for which we previously had absolutely no data. Those ranges are now trial factored thru 2^47 or 2^52, primarily by Jean-Charles. The '2 new' at the end are mine, more or less by accident when something ran faster than I expected. The smallest ten incompletely factored prime exponent Mersenne numbers are now 601 617 619 631 641 643 673 677 683 719. The smallest ten with no known factors are 727 751 809 971 983 997 1061 1237 1277 1283. Chad Davis sent in some new Factor95 factors on the 15th & 16th of March: M23201 has a factor: 23297052050119327 M23623 has a factor: 28702685058745471 M8081 has a factor: 1343743045821830104657 On the 19th, Rob Hooft sent a couple of factors found using GMP-ECM: M( 2143 )C: 5583850438566365729 Leaves C600 M( 2251 )C: 1687942505818611032423917201 Leaves C639 On the 21st, Conrad Curry sent one from GMP-ECM and three from Factor95: M2143 has a factor: 5583850438566365729 M6113 has a factor: 372190698305357447233 M6217 has a factor: 2941232948099472833 M6263 has a factor: 170489085677393436641 Ernst Mayer reported a new first factor from stage one of his P-1 program to the mailing list on 6 April: 3109 2542642069261987144201. C914 noting that P-1 = 2^3*3*5^2*7*3109*1356763*143519603. On April 7th, Paul Zimmerman reported the completed factorization of M(613) after his GMP-ECM printed: Found probable prime factor: 332817722770314187794325446534549089 Steven Whitaker reported five Factor95 discoveries on the 8th: M5387 has a factor: 121180963479604713799 M5569 has a factor: 755152784431796452276081311289 M5573 has a factor: 41382017328569838736935649 M5653 has a factor: 243961562458195079 M5981 has a factor: 5813193849719234279887 Jean-Charles Meyrignac sent a new Factor95 factor on each of the 9th and the 16th and three more on the 17th: M8779 has a factor: 37597094445244247 M16223 has a factor: 1081725837328719625226183 M8629 has a factor: 10090322280381743 M8893 has a factor: 5175359424350473 M10957 has a factor: 39774345654081910639 Conrad Curry sent the newly complete factorizations of M661 (on the 12th, by step one of GMP-ECM) and M659 (on the 22nd, by step 2). The new factors are: M( 661 )C: 118420287267066844820208926433723871 M( 659 )C: 626564962613678012662146877852049 for which he noted that, respectively: P-1 = 2^6*3^2*5^2*7*47*479*661*7529*13399*26083*31237*960493 P-1 = 2^4*7*347*659*52031587*105065377*4475138677 As he pointed out explicitly in the second message, P-1 had thus not been run very far for the small exponent Mersennes; that is being corrected. Up to this time, I had been under the impression that the Cunningham Project, if noone else, had run the exponents under 1200 to P-1 stage one depths of at least 10^9. David Campeau sent five new Factor98 factors on the 20th: M( 25321 )C: 476514964764436079 M( 21499 )C: 316949300616141588953 M( 21673 )C: 689220685290271369 M( 22189 )C: 255208363280070439 M( 23561 )C: 136521758696636230204513 Rob Hooft, also on the 20th, sent new three GMP-ECM factors: M( 2621 )C: 13489674267041509343311 (Cofactor is a C756) M( 2659 )C: 292005484799111903 (Cofactor is a C769) M( 2663 )C: 3939912086508906841 (Cofactor is a C772) Still on the 20th, Eric Prestemon sent a GMP-ECM factor and two more (one by GMP-ECM and one by Factor95) on the 23rd: M( 1783 )C: 60701317462845977755176049 M( 1447 )C: 135870799392023187135247 M( 1481 )C: 3993419580376129303010329 On the 22nd, Jean-Charles Meyrignac sent two more new P-1 Factor95 results: M4493 has a factor: 6393188928634500752988047 M8693 has a factor: 358540678934355598073 and then, two days later, the new factor of M(1481) already sent by Eric on the day in between. Eric sent another Factor95 result on the 24th: M10009 has a factor: 890928517778601397463 Lastly, Chad Davis sent a new P-1 factor earlier today (April 25th): M25621 has a factor: 1339691475108407 Will http://www.garlic.com/~wedgingt/mersenne.html lowM.txt factoredM.txt primeM.txt mersfmt.txt The first has links to several other Mersenne and GIMPS related pages. The last tries to explain the formats used in lowM.txt and factoredM.txt, which two contain all data known to me for incompletely and completely, respectively, factored Mersenne composites. PrimeM.txt contains the exponents of the known Mersenne primes. ------------------------------ From: Will Edgington Date: Sat, 25 Apr 1998 15:46:23 -0700 Subject: Mersenne: P-1 factoring "meta-info" Several people have apparently gotten confused recently because there's no way to reserve exponents to do P-1 factoring on Conrad Curry's web pages. Please continue to send email directly to me to reserve exponents. I will likely share this reservation data with Conrad in the future, so if you don't want me to share your reservations or email address with him, let me know soon. I hope to automate the reservation process in the future, but I presently do not have time to work on it. Also, I have recently decided to accept P-1 "save" or "continuation" files via email. I can handle MIME, zip, tar, gzip, btoa, uuencode, and several other formats and encoding methods. Please only send save files for exponents that you are no longer going to work on. Feel free to send "results" files at any time, either to me via email or to Conrad Curry's web site, which I believe is at: http://ocean.st.usm.edu/~cwcurry/update.html ... but either that host or the network is down as I type this. Please send all new factors to me; I do not recall whether Conrad's web site handles them or not. With the new interest in P-1 factoring of small exponents after the recent complete factorizations of three under 600, I will probably hand out smaller ranges from now on, especially for exponents under 3000 or so. Presently, the available ranges are 2000 thru 2700, 6000 thru 8190, 16418 thru 20000, 32000 thru 86000, and almost everything above 87000. I have no save files for any exponents. Lastly, there has been a proposal to randomly assign exponents under 1500 or so one per computer at a time so that more people have the chance to factor the smallest incompletely factored exponents. Will P.S. If 'fizban' is out there, could you send me email? I do not seem to have a valid address for you and would like to know what recent progress you've made with Factor95 on your exponents. ------------------------------ From: Walt Mankowski Date: Sat, 25 Apr 1998 21:18:18 -0400 (EDT) Subject: Mersenne: Rolling Average What does the "RollingAverage" field in local.ini field mean? Sorry if this has been discussed before. I'm new to the project and I couldn't find it in the FAQ. Walt Mankowski waltman@netaxs.com ------------------------------ From: Walt Mankowski Date: Sat, 25 Apr 1998 21:30:15 -0400 (EDT) Subject: Mersenne: Factoring Algorithm There is a lot of information on the GIMPS homepage and in the readme.txt file about the Lucas-Lehmer algorithm, but I can't find any information about how the initial factoring algorithm works. Can anyone point me to some links? Thanks. Walt Mankowski waltman@netaxs.com ------------------------------ From: Warut Roonguthai Date: Sun, 26 Apr 1998 11:36:02 +0700 (ICT) Subject: Mersenne: Repunit Primes Once there was a good page about generalized repunit primes by one of GIMPS members (can't recall whom) at http://www.rosenheim.baynet.de/~karoli01/pgmprim1.html Does anyone know where it is now? Thanks in advance. ------------------------------ End of Mersenne Digest V1 #351 ******************************