Mersenne Digest Tuesday, December 23 2003 Volume 01 : Number 1098
---------------------------------------------------------------------- Date: Sat, 13 Dec 2003 13:48:51 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Mersenne: Another thought on the L-L Test Hi, Another thought struck me - this could have useful applications in L-L testing programs. If M is the Mersenne number being tested & R(i) is the L-L residue after i iterations, then R(i+1) = R(i) * R(i) - 2 (modulo M) (by the statement of the L-L algorithm) But note that (M - R(i))^2 - 2 = M^2 - 2MR(i) + R(i)^2 - 2 so (M-R(i))^2 - 2 (modulo M) is clearly equal to R(i+1). How can this be of any use? Well, when we have a dubious iteration (say an excessive roundoff or sum error) we can check the output by redoing the last iteration but starting from (M-R(i)) instead of R(i) - the output should be the same. Furthermore the action of calculating M-R(i) is very easy - just invert all the bits. Also, if we have suspicions about the accuracy of code when there is a high density of 1 bits, we can try just one iteration but starting at M-4 instead of 4. The output residual should be 14 irrespective of M (providing M>7 - as will often be the case!). The point here is that, just as the value 4 is represented by a string of p bits only one of which is set, M-4 is represented by a string of p bits only one of which is unset. Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 13 Dec 2003 19:08:10 +0100 From: Alexander Kruppa <[EMAIL PROTECTED]> Subject: Re: Mersenne: Possible refinement of screening for Mersenne primes Alexander Kruppa wrote: > Brian J. Beesley wrote: > >> Hi, >> > >> (1) Could someone with the required background please tidy up my logic >> and prove that the assertion above is true i.e. there is no prime >> 2^p-1 with p > 3 such that there are solutions to x^2 mod 2^p-1 = >> 2^((p+1)/2) + 2 > > > > I believe the idea is correct, but it doesn't remove candidates. > > Lets try (going out on a limb here, fingers crossed): > > [...] > > If p>3 and odd, 2^((p+1)/2) + 2 (mod 2^p-1) is always a QR. That is rubbish. I was misusing the Kroecker symbol and the conclusion is wrong. (The fact that your list contained several counterexamples should have been a strong hint!) What my argument shows is that the number of prime factors of Mp for which [+-]2^((p+1)/2) + 2 are QNR is always even. But that doesn't tell us whether they are QR (mod Mp) or not, i.e. whether they are QR modulo *every* prime factor, unless of course Mp is prime and both must be QR modulo the only prime "factor" there is. Since (2^((p+1)/2) + 2) * (-2^((p+1)/2) + 2) == -2^(p+1) + 4 == -2 + 4 == 2 (mod f) for any f|Mp, and 2 is a QR (mod f), [+-]2^((p+1)/2) + 2 must be either both be QR or QNR. So it suffices to check only one. To determine whether or not they are QR (mod Mp) via quadratic reciprocity would require knowing the prime factorization of Mp - and knowing even one nontrivial factor would of course settle the question of primality as well. One could use Euler's criterion as a check: if q is prime and gcd(r,q)==1, r^((q-1)/2) == 1 (mod q) if r is a QR, and == -1 otherwise. If q is not prime, the result will usually be neither 1 or -1. We already know that 2^((p+1)/2) + 2 is a QR if Mp is prime, so this check will really just be a Fermat-style probable prime test which takes just as long as a LL test, but doesn't prove primality. I've made a list of Mp, p<200, that are not Mersenne primes, and the Kronecker symbol (or Legendre, actually) of 2^((p+1)/2) + 2 (mod f) for each prime factor f of Mp. It shows that knowing whether [+-]2^((p+1)/2) + 2 is a QR would really eliminate a lot of candidates - M_23, M_37, M_47, M_59, M_101, M_137, M_139, M_149, M_167, M_181, M_193, M_197, M199 would survive the test, while M_11, M_29, M_41, M_43, M_53, M_67, M_71, M_73, M_79, M_83, M_97, M_103, M_109, M_113, M_131, M_151, M_157, M_163, M_173, M_179, M_191 could be indentifed as composite. Your question (2) remains open - is there a faster way to determine whether 2^((p+1)/2) + 2 is a QR (mod Mp) than running a LL test? When a composite Mp is completely factored, it is very easy to determine whether 2^((p+1)/2) + 2 is a QR. With enough composite Mp completely factored, maybe some kind of pattern can be discovered in the exponents p for which it is or isn't a QR? Alex M_11: ( 2^6+2 | 23 ) = -1 M_11: ( 2^6+2 | 89 ) = -1 M_23: ( 2^12+2 | 47 ) = 1 M_23: ( 2^12+2 | 178481 ) = 1 M_29: ( 2^15+2 | 233 ) = -1 M_29: ( 2^15+2 | 1103 ) = 1 M_29: ( 2^15+2 | 2089 ) = -1 M_37: ( 2^19+2 | 223 ) = 1 M_37: ( 2^19+2 | 616318177 ) = 1 M_41: ( 2^21+2 | 13367 ) = -1 M_41: ( 2^21+2 | 164511353 ) = -1 M_43: ( 2^22+2 | 431 ) = 1 M_43: ( 2^22+2 | 9719 ) = -1 M_43: ( 2^22+2 | 2099863 ) = -1 M_47: ( 2^24+2 | 2351 ) = 1 M_47: ( 2^24+2 | 4513 ) = 1 M_47: ( 2^24+2 | 13264529 ) = 1 M_53: ( 2^27+2 | 6361 ) = -1 M_53: ( 2^27+2 | 69431 ) = -1 M_53: ( 2^27+2 | 20394401 ) = 1 M_59: ( 2^30+2 | 179951 ) = 1 M_59: ( 2^30+2 | 3203431780337 ) = 1 M_67: ( 2^34+2 | 193707721 ) = -1 M_67: ( 2^34+2 | 761838257287 ) = -1 M_71: ( 2^36+2 | 228479 ) = 1 M_71: ( 2^36+2 | 48544121 ) = -1 M_71: ( 2^36+2 | 212885833 ) = -1 M_73: ( 2^37+2 | 439 ) = -1 M_73: ( 2^37+2 | 2298041 ) = -1 M_73: ( 2^37+2 | 9361973132609 ) = 1 M_79: ( 2^40+2 | 2687 ) = 1 M_79: ( 2^40+2 | 202029703 ) = -1 M_79: ( 2^40+2 | 1113491139767 ) = -1 M_83: ( 2^42+2 | 167 ) = -1 M_83: ( 2^42+2 | 57912614113275649087721 ) = -1 M_97: ( 2^49+2 | 11447 ) = -1 M_97: ( 2^49+2 | 13842607235828485645766393 ) = -1 M_101: ( 2^51+2 | 7432339208719 ) = 1 M_101: ( 2^51+2 | 341117531003194129 ) = 1 M_103: ( 2^52+2 | 2550183799 ) = -1 M_103: ( 2^52+2 | 3976656429941438590393 ) = -1 M_109: ( 2^55+2 | 745988807 ) = -1 M_109: ( 2^55+2 | 870035986098720987332873 ) = -1 M_113: ( 2^57+2 | 3391 ) = 1 M_113: ( 2^57+2 | 23279 ) = 1 M_113: ( 2^57+2 | 65993 ) = -1 M_113: ( 2^57+2 | 1868569 ) = -1 M_113: ( 2^57+2 | 1066818132868207 ) = 1 M_131: ( 2^66+2 | 263 ) = -1 M_131: ( 2^66+2 | 10350794431055162386718619237468234569 ) = -1 M_137: ( 2^69+2 | 32032215596496435569 ) = 1 M_137: ( 2^69+2 | 5439042183600204290159 ) = 1 M_139: ( 2^70+2 | 5625767248687 ) = 1 M_139: ( 2^70+2 | 123876132205208335762278423601 ) = 1 M_149: ( 2^75+2 | 86656268566282183151 ) = 1 M_149: ( 2^75+2 | 8235109336690846723986161 ) = 1 M_151: ( 2^76+2 | 18121 ) = -1 M_151: ( 2^76+2 | 55871 ) = 1 M_151: ( 2^76+2 | 165799 ) = -1 M_151: ( 2^76+2 | 2332951 ) = -1 M_151: ( 2^76+2 | 7289088383388253664437433 ) = -1 M_157: ( 2^79+2 | 852133201 ) = 1 M_157: ( 2^79+2 | 60726444167 ) = -1 M_157: ( 2^79+2 | 1654058017289 ) = -1 M_157: ( 2^79+2 | 2134387368610417 ) = 1 M_163: ( 2^82+2 | 150287 ) = 1 M_163: ( 2^82+2 | 704161 ) = 1 M_163: ( 2^82+2 | 110211473 ) = 1 M_163: ( 2^82+2 | 27669118297 ) = -1 M_163: ( 2^82+2 | 36230454570129675721 ) = -1 M_167: ( 2^84+2 | 2349023 ) = 1 M_167: ( 2^84+2 | 79638304766856507377778616296087448490695649 ) = 1 M_173: ( 2^87+2 | 730753 ) = 1 M_173: ( 2^87+2 | 1505447 ) = -1 M_173: ( 2^87+2 | 70084436712553223 ) = -1 M_173: ( 2^87+2 | 155285743288572277679887 ) = 1 M_179: ( 2^90+2 | 359 ) = -1 M_179: ( 2^90+2 | 1433 ) = -1 M_179: ( 2^90+2 | 1489459109360039866456940197095433721664951999121 ) = 1 M_181: ( 2^91+2 | 43441 ) = 1 M_181: ( 2^91+2 | 1164193 ) = 1 M_181: ( 2^91+2 | 7648337 ) = 1 M_181: ( 2^91+2 | 7923871097285295625344647665764672671 ) = 1 M_191: ( 2^96+2 | 383 ) = 1 M_191: ( 2^96+2 | 7068569257 ) = -1 M_191: ( 2^96+2 | 39940132241 ) = 1 M_191: ( 2^96+2 | 332584516519201 ) = 1 M_191: ( 2^96+2 | 87274497124602996457 ) = -1 M_193: ( 2^97+2 | 13821503 ) = 1 M_193: ( 2^97+2 | 61654440233248340616559 ) = 1 M_193: ( 2^97+2 | 14732265321145317331353282383 ) = 1 M_197: ( 2^99+2 | 7487 ) = 1 M_197: ( 2^99+2 | 26828803997912886929710867041891989490486893845712448833 ) = 1 M_199: ( 2^100+2 | 164504919713 ) = 1 M_199: ( 2^100+2 | 4884164093883941177660049098586324302977543600799 ) = 1 _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 14 Dec 2003 10:21:51 -0600 From: Stephen Whitis <[EMAIL PROTECTED]> Subject: Mersenne: Smallest Prime Number Discovered, Soon After Largest From a Satire site... http://theeschalot.com/smallest-prime-number-discovered.html Smallest Prime Number Discovered, Soon After Largest DETROIT - Wallace Bonownski says you don't have to have 200,000 computers and a grad student to discover a new prime number. "You just gotta use yer thinker, is all," said the Michigan State University groundskeeper. "I heard about Michael's big find, and I thought, 'Hey, if that's the largest prime number, then I'll bet the negative version would be the smallest. And I discovered it!'" (continues) _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 14 Dec 2003 07:03:33 -0600 From: [EMAIL PROTECTED] (Mikus Grinbergs) Subject: Mersenne: PrimeNet response Was using the PrimeNet manual entry page. It responded as expected to my input, but the response included the line ----- rate regulated at 0.50 Hz ----- What is that line telling me ??? mikus _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 23 Dec 2003 10:42:45 +0000 From: Nick Craig-Wood <[EMAIL PROTECTED]> Subject: Mersenne: Large memory pages in Linux On Wed, Dec 10, 2003 at 06:26:54PM +0000, Nick Craig-Wood wrote: > I'm in the process of writing (not quite finished or working ;-) some > code which you load as an LD_PRELOAD library under linux. This gets > its fingers into the memory allocation, and makes all malloc space > come from hugetlbfs (how you get large pages under linux). > > My primary user for this was to be mprime of course! Well I finished the code and here are the results on my lowly laptop running 2.6.0. Intel(R) Pentium(R) III processor CPU speed: 550.78 MHz CPU features: RDTSC, CMOV, PREFETCH, MMX, SSE L1 cache size: 16 KB L2 cache size: 256 KB L1 cache line size: 32 bytes L2 cache line size: 32 bytes TLBS: 64 Prime95 version 22.12, RdtscTiming=1 Normal - ------ Best time for 256K FFT length: 80.256 ms. Best time for 320K FFT length: 101.820 ms. Best time for 384K FFT length: 125.191 ms. Best time for 448K FFT length: 145.505 ms. Best time for 512K FFT length: 161.178 ms. Best time for 640K FFT length: 215.113 ms. Best time for 768K FFT length: 258.055 ms. Best time for 896K FFT length: 304.786 ms. Best time for 1024K FFT length: 345.747 ms. Best time for 1280K FFT length: 449.540 ms. Best time for 1536K FFT length: 541.963 ms. Best time for 1792K FFT length: 661.651 ms. With all memory allocations coming from 4 MB pages - -------------------------------------------------- Best time for 256K FFT length: 79.293 ms. 1.2% Best time for 320K FFT length: 102.032 ms. -0.2% Best time for 384K FFT length: 124.022 ms. 0.9% Best time for 448K FFT length: 145.492 ms. 0.0% Best time for 512K FFT length: 161.568 ms. -0.2% Best time for 640K FFT length: 213.311 ms. 0.8% Best time for 768K FFT length: 254.609 ms. 1.3% Best time for 896K FFT length: 301.911 ms. 0.9% Best time for 1024K FFT length: 339.203 ms. 1.9% Best time for 1280K FFT length: 439.119 ms. 2.3% Best time for 1536K FFT length: 531.422 ms. 1.9% Best time for 1792K FFT length: 645.350 ms. 2.5% So consistent but small improvements in the larger FFTs. This just goes to show what a good job George has done in not thrashing the TLB! I wonder if Prime95 could be made more efficient if it didn't have to worry about the TLB? Its obviously detecting the TLB slots for this computer which is wrong in this case - perhaps there is a way of overriding this? Please email me if you'd like to experiment with the code - its quite simple (it just took rather a lot of different approaches to get right!). You'll need to be running 2.6.0 with HUGETLB support if you want to play (see hugetlbpage.txt in Documentation in the kernel source for more info). - -- Nick Craig-Wood [EMAIL PROTECTED] _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #1098 *******************************
