Mersenne Digest Saturday, December 13 2003 Volume 01 : Number 1097
---------------------------------------------------------------------- Date: Wed, 10 Dec 2003 18:26:54 +0000 From: Nick Craig-Wood <[EMAIL PROTECTED]> Subject: Re: Mersenne: Large memory pages in Linux and Windows Server (64bit?) On Wed, Dec 10, 2003 at 02:50:11PM +0100, Matthias Waldhauer wrote: > Back to the topic: > Some time ago there was a discussion going on regarding the use of large > memory pages. In a mersenneforum thread I collected some info regarding > new linux kernels and some real world results published in a paper. > > Here some extracts: > Linux kernel versions 2.5.36+ and 2.6 include a "HugeTLBs" patch, which > allows an application to allocate large memory pages. > Also 64bit Windows Server seems to support them too: > http://msdn.microsoft.com/library/default.asp?url=/library/en-us/memory/base/large_page_support.asp > > My thoughts about the possilibities: > Oracle managed to get a 8% speedup by using the large pages. Although I > have little experience in this area I think for FFTs the speedup will be > much larger [snip] I agree! I have been thinking about the exact same thing. 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! When finished this should be an easy way of trying any application with large pages without having to modify it. I haven't finished the code yet, but it shouldn't take long, especially if people are asking for it! - -- 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 ------------------------------ Date: Thu, 11 Dec 2003 14:20:41 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Mersenne: Possible refinement of screening for Mersenne primes Hi, I was thinking about the possible reversibility of the Lucas Lehmer algorithm. In particular, for any odd number n > 1, (2^((n+1)/2))^2 is congruent to 2 modulo 2^n-1 i.e. 2 is a quadratic residue modulo 2^n-1. This is not helpful in itself as (a) there are other integer solutions to sqrt(x + k.2^n-1) = 2, (b) it does not distinguish in any way between prime and composite Mersenne numbers. However, considering the next-to-the-last iteration appears to be interesting. If x is a solution to (x^2 - 2) mod (2^n-1) = 2^((n+1)/2) then starting from residue x and performing 2 iterations will result in residue 0. For small n>3 (n=3 does not work because there is only one iteration to do in the L-L test!) we have: n = 5: x^2-2 mod 31 = 8; x^2 mod 31 = 10; x = 14, x = 17 n = 7: x^2-2 mod 127 = 16; x^2 mod 127 = 18; x = 48, x = 79 n = 9: x^2-2 mod 511 = 32; x^2 mod 511 = 34; no solutions n = 11: x^2 - 2 mod 2047 = 64; x^2 mod 2047 = 68; no solutions n = 13; x^2 - 2 mod 8191 = 128; x^2 mod 8191 = 130; x = 3470, x = 4721 n = 15; x^2 - 2 mod 32767 = 256; x^2 mod 32767 = 258; no solutions n = 17; x^2 - 2 mod 131071 = 512; x^2 mod 131071 = 514; x = 19647, x = 111424 n = 19; x^2 mod 524287 = 1026; x = 199279, x = 325008 n = 21; x^2 mod 2^21-1 = 2050; no solutions n = 23; x^2 mod 2^23-1 = 4098; x = 2339992, x = 3053916, x = 5334691, x = 6048615 In other words, it looks as if when there are no solutions to x^2 mod 2^n-1 = 2^((n+1)/2) + 2, then 2^n-1 is not prime, although the converse is not neccessarily true. (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 If so, then we have a "one-step" test which would allow us to eliminate some - - possibly many - Mersenne prime candidates without even bothering to look for small factors. (2) Can it be demonstrated that the search for solutions of x^2 mod 2^p-1 = 2^((p+1)/2) + 2 - or at least the search for _existence_ of solutions (we wouldn't need the actual numerical values) - might be faster than executing the LL test? The method I used for small n above was just to step through values of k calculating k^2 mod 2^n-1, which is clearly exceedingly _in_efficient for large n! Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 11 Dec 2003 14:20:41 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Mersenne: Possible refinement of screening for Mersenne primes Hi, I was thinking about the possible reversibility of the Lucas Lehmer algorithm. In particular, for any odd number n > 1, (2^((n+1)/2))^2 is congruent to 2 modulo 2^n-1 i.e. 2 is a quadratic residue modulo 2^n-1. This is not helpful in itself as (a) there are other integer solutions to sqrt(x + k.2^n-1) = 2, (b) it does not distinguish in any way between prime and composite Mersenne numbers. However, considering the next-to-the-last iteration appears to be interesting. If x is a solution to (x^2 - 2) mod (2^n-1) = 2^((n+1)/2) then starting from residue x and performing 2 iterations will result in residue 0. For small n>3 (n=3 does not work because there is only one iteration to do in the L-L test!) we have: n = 5: x^2-2 mod 31 = 8; x^2 mod 31 = 10; x = 14, x = 17 n = 7: x^2-2 mod 127 = 16; x^2 mod 127 = 18; x = 48, x = 79 n = 9: x^2-2 mod 511 = 32; x^2 mod 511 = 34; no solutions n = 11: x^2 - 2 mod 2047 = 64; x^2 mod 2047 = 68; no solutions n = 13; x^2 - 2 mod 8191 = 128; x^2 mod 8191 = 130; x = 3470, x = 4721 n = 15; x^2 - 2 mod 32767 = 256; x^2 mod 32767 = 258; no solutions n = 17; x^2 - 2 mod 131071 = 512; x^2 mod 131071 = 514; x = 19647, x = 111424 n = 19; x^2 mod 524287 = 1026; x = 199279, x = 325008 n = 21; x^2 mod 2^21-1 = 2050; no solutions n = 23; x^2 mod 2^23-1 = 4098; x = 2339992, x = 3053916, x = 5334691, x = 6048615 In other words, it looks as if when there are no solutions to x^2 mod 2^n-1 = 2^((n+1)/2) + 2, then 2^n-1 is not prime, although the converse is not neccessarily true. (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 If so, then we have a "one-step" test which would allow us to eliminate some - - possibly many - Mersenne prime candidates without even bothering to look for small factors. (2) Can it be demonstrated that the search for solutions of x^2 mod 2^p-1 = 2^((p+1)/2) + 2 - or at least the search for _existence_ of solutions (we wouldn't need the actual numerical values) - might be faster than executing the LL test? The method I used for small n above was just to step through values of k calculating k^2 mod 2^n-1, which is clearly exceedingly _in_efficient for large n! 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: Thu, 11 Dec 2003 16:39:32 +0100 From: [EMAIL PROTECTED] Subject: Mersenne: Penultimate Lucas-Lehmer step Let p > 2 be prime and Mp = 2^p - 1. The familiar Lucas-Lehmer test sets a[0] = 4 and a[j+1] = a[j]^2 - 2 for j >= 0. Mp is prime if and only if a[p-1] == 0 mod Mp. When Mp is prime, then a[p-2]^2 == 2 == 2*Mp + 2 = 2^(p+1) (mod Mp). Taking square roots, either a[p-2] == 2^((p+1)/2) mod Mp or a[p-2] == -2^((p+1)/2) mod Mp. Around 20 years ago I heard that nobody could predict which of these would occur. For example, p = 3 a[1] = 4 == 2^2 (mod 7) p = 5 a[3] = 194 == 2^3 (mod 31) p = 7 a[5] = 1416317954 == -2^4 (mod 127). Now that 40 Mersenne primes are known, can anyone extend this table further? That will let us test heuristics, such as whether both +- 2^((p+1)/2) seem to occur 50% of the time, and provide data to support or disprove conjectures. Peter Montgomery _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 11 Dec 2003 18:10:20 +0100 From: Alexander Kruppa <[EMAIL PROTECTED]> Subject: Re: Mersenne: Possible refinement of screening for Mersenne primes 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): Is 2^((p+1)/2) + 2 (mod 2^p-1) a QR? We can rewrite as 2*(2^((p-1)/2) + 1) (mod 2^p-1) and that is a QR iff 2^((p-1)/2) + 1 (mod 2^p-1) is, as 2 is a QR and quadratic character is multiplicative. ( 2^((p-1)/2) + 1 ) (-----------------) (Kronecker symbol) ( 2^p-1 ) ( (2^p-1) % 2^((p-1)/2) + 1 ) = (---------------------------) ( 2^((p-1)/2) + 1 ) because 2^((p-1)/2) + 1 == 1 (mod 4) if p>3 and odd, and (2^p-1)-1 = 2*(2^(p-1)-1) = 2*(2^((p-1)/2)-1)(2^((p-1)/2)+1), therefore 2^((p-1)/2) + 1 | (2^p-1)-1, (2^p-1)-1 == 0 (mod 2^((p-1)/2) + 1) and thus 2^p-1 == 1 (mod 2^((p-1)/2) + 1). It follows ( 1 ) = (-----------------) = 1 ( 2^((p-1)/2) + 1 ) If p>3 and odd, 2^((p+1)/2) + 2 (mod 2^p-1) is always a QR. For the other sqrt(2), -2^((p+1)/2), the question is: Is -2^((p+1)/2) + 2 a QR? We can reqrite as (-1)*(2)*(2^((p-1)/2) - 1), since 2^p-1 == 3 (mod 4), - -1 is a QNR and so ( -2^((p+1)/2) + 2 ) ( 2^((p-1)/2) - 1 ) (------------------) = - (-----------------) ( 2^p-1 ) ( 2^p-1 ) Since both 2^((p-1)/2) - 1 and 2^p-1 are == 3 (mod 4) for odd p>3, quadratic reciprocity introduces another sign change, thus ( (2^p-1) % 2^((p-1)/2) - 1 ) = (---------------------------) ( 2^((p-1)/2) - 1 ) 2^((p-1)/2) - 1 | (2^p-1)-1 as seen before, so ( 1 ) = (-----------------) = 1 ( 2^((p-1)/2) - 1 ) If p>3 and odd, -2^((p+1)/2) + 2 (mod 2^p-1) is always a QR. Is there a better (or if applicable, correct) proof? Can, for example, sqrt([+/-]2^((p+1)/2) + 2) in Z/Z(2^p-1) be given explicitly, like sqrt(2) can? Alex _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 11 Dec 2003 09:23:17 -0800 From: Luke Welsh <[EMAIL PROTECTED]> Subject: Re: Mersenne: Penultimate Lucas-Lehmer step At 04:39 PM 12/11/03 +0100, [EMAIL PROTECTED] wrote: > When Mp is prime, then > > a[p-2]^2 == 2 == 2*Mp + 2 = 2^(p+1) (mod Mp). > >Taking square roots, either > > a[p-2] == 2^((p+1)/2) mod Mp >or > a[p-2] == -2^((p+1)/2) mod Mp. > >Around 20 years ago I heard that nobody could predict >which of these would occur. After M29 was discovered, that was the very first question Dick Lehmer asked. I think it interested him more than the value of p!! - --Luke _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 12 Dec 2003 06:59:09 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Penultimate Lucas-Lehmer step On Thursday 11 December 2003 15:39, [EMAIL PROTECTED] wrote: > Let p > 2 be prime and Mp = 2^p - 1. > The familiar Lucas-Lehmer test sets a[0] = 4 > and a[j+1] = a[j]^2 - 2 for j >= 0. > Mp is prime if and only if a[p-1] == 0 mod Mp. > > When Mp is prime, then > > a[p-2]^2 == 2 == 2*Mp + 2 = 2^(p+1) (mod Mp). > > Taking square roots, either > > a[p-2] == 2^((p+1)/2) mod Mp > or > a[p-2] == -2^((p+1)/2) mod Mp. > > > Around 20 years ago I heard that nobody could predict > which of these would occur. For example, > > p = 3 a[1] = 4 == 2^2 (mod 7) > p = 5 a[3] = 194 == 2^3 (mod 31) > p = 7 a[5] = 1416317954 == -2^4 (mod 127). > > Now that 40 Mersenne primes are known, can anyone > extend this table further? That will let us test > heuristics, such as whether both +- 2^((p+1)/2) > seem to occur 50% of the time, and > provide data to support or disprove conjectures. > This is dependent on using the Lucas sequence starting at 4. In practice there are a large number of other starting values which could be used - in fact, 2^(p-2) of them. AFAIK we happen to use 4 because it is a "nice small number" which works for all values of p > 2 - whereas most of the other values which work for p don't neccessarily work for q != p. For instance, with p=3 we could use starting value 3 instead of 4 3^2 - 2 = 7 is congruent to 0 modulo 2^3-1 4^2 - 2 = 14 is congruent to 0 modulo 2^3-1 But other values don't work: 0^2 - 2 = -2 is congruent to 5 modulo 2^3-1 1^2 - 2 = -1 is congruent to 6 modulo 2^3-1 2^2 - 2 = 2 is congruent to 2 modulo 2^3-1 5^2 - 2 = 23 is congruent to 2 modulo 2^3-1 6^2 - 2 = 34 is congruent to 6 modulo 2^3-1 Obviously enough, if k is a quadratic residue modulo n. then so is n-k (n-k)^2 mod n = n^2 -2kn +k^2 mod n = k^2 mod n So, in the penultimate step, it _doesn't matter_ whether the actual residue is 2^((p+1)/2) or -2^((p+1)/2) - if running one iteration from 2^((p+1)/2) doesn't give residue 0, then neither can running one interation from - -2((p+1)/2), and vice versa. So simply testing whether 2^((p+1)/2)+2 is a quadratic residue modulo 2^p-1 _might_ (in principle) be helpful. Look in particular at p=11. 2^6+2 = 66 (not 68 as misprinted in my previous message) appears not to be a quadratic residue modulo 2^11-1 = 2047 and sure enough 2^11-1 is composite. Interestingly there are _two_ distinct solutions to x^2 mod 2^23-1 = 2^12+2: x=+/-2339992 & x=+/-3053916. This suggests that the number of starting values for a "successful" L-L test might _exceed_ 2^(p-2) by a factor of _at least_ 2 i.e. every possible starting value would have to reach 0 after p-2 iterations - which is clearly absurd. So perhaps the criterion should be that there is only one _distinct_ solution to sqrt (2^(p+1)/2)+2) modulo 2^p-1. Anyhow if we "play safe" we simply find that, in the case p=23, 4098 is a quadratic residue mod 8388607, so we have to run a LL test. Unless we happen to notice that 23 is a 3 mod 4 Sophie-Germain prime so 8388607 is divisible by 47.... Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 12 Dec 2003 06:59:09 +0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Penultimate Lucas-Lehmer step On Thursday 11 December 2003 15:39, [EMAIL PROTECTED] wrote: > Let p > 2 be prime and Mp = 2^p - 1. > The familiar Lucas-Lehmer test sets a[0] = 4 > and a[j+1] = a[j]^2 - 2 for j >= 0. > Mp is prime if and only if a[p-1] == 0 mod Mp. > > When Mp is prime, then > > a[p-2]^2 == 2 == 2*Mp + 2 = 2^(p+1) (mod Mp). > > Taking square roots, either > > a[p-2] == 2^((p+1)/2) mod Mp > or > a[p-2] == -2^((p+1)/2) mod Mp. > > > Around 20 years ago I heard that nobody could predict > which of these would occur. For example, > > p = 3 a[1] = 4 == 2^2 (mod 7) > p = 5 a[3] = 194 == 2^3 (mod 31) > p = 7 a[5] = 1416317954 == -2^4 (mod 127). > > Now that 40 Mersenne primes are known, can anyone > extend this table further? That will let us test > heuristics, such as whether both +- 2^((p+1)/2) > seem to occur 50% of the time, and > provide data to support or disprove conjectures. > This is dependent on using the Lucas sequence starting at 4. In practice there are a large number of other starting values which could be used - in fact, 2^(p-2) of them. AFAIK we happen to use 4 because it is a "nice small number" which works for all values of p > 2 - whereas most of the other values which work for p don't neccessarily work for q != p. For instance, with p=3 we could use starting value 3 instead of 4 3^2 - 2 = 7 is congruent to 0 modulo 2^3-1 4^2 - 2 = 14 is congruent to 0 modulo 2^3-1 But other values don't work: 0^2 - 2 = -2 is congruent to 5 modulo 2^3-1 1^2 - 2 = -1 is congruent to 6 modulo 2^3-1 2^2 - 2 = 2 is congruent to 2 modulo 2^3-1 5^2 - 2 = 23 is congruent to 2 modulo 2^3-1 6^2 - 2 = 34 is congruent to 6 modulo 2^3-1 Obviously enough, if k is a quadratic residue modulo n. then so is n-k (n-k)^2 mod n = n^2 -2kn +k^2 mod n = k^2 mod n So, in the penultimate step, it _doesn't matter_ whether the actual residue is 2^((p+1)/2) or -2^((p+1)/2) - if running one iteration from 2^((p+1)/2) doesn't give residue 0, then neither can running one interation from - -2((p+1)/2), and vice versa. So simply testing whether 2^((p+1)/2)+2 is a quadratic residue modulo 2^p-1 _might_ (in principle) be helpful. Look in particular at p=11. 2^6+2 = 66 (not 68 as misprinted in my previous message) appears not to be a quadratic residue modulo 2^11-1 = 2047 and sure enough 2^11-1 is composite. Interestingly there are _two_ distinct solutions to x^2 mod 2^23-1 = 2^12+2: x=+/-2339992 & x=+/-3053916. This suggests that the number of starting values for a "successful" L-L test might _exceed_ 2^(p-2) by a factor of _at least_ 2 i.e. every possible starting value would have to reach 0 after p-2 iterations - which is clearly absurd. So perhaps the criterion should be that there is only one _distinct_ solution to sqrt (2^(p+1)/2)+2) modulo 2^p-1. Anyhow if we "play safe" we simply find that, in the case p=23, 4098 is a quadratic residue mod 8388607, so we have to run a LL test. Unless we happen to notice that 23 is a 3 mod 4 Sophie-Germain prime so 8388607 is divisible by 47.... 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: Fri, 12 Dec 2003 13:14:33 +0100 (MET) From: Wojciech Florek <[EMAIL PROTECTED]> Subject: Mersenne: Generalized Mersenne Numbers Hi! Jean Penne has written about 3^n-2. I've played for a while with 5^n-(5-1)^5=5^n-1024. Of course, for n=5k they are composite; since 4=2^2 they are also composite for even n. Moreover, there are some series of composite numbers, e.g. for n=10,16,22,28,... they are divisible by 7 (it can be proven), and for n=3k d=31 is a divisor (I had no time to prove it, but it is easy, I think). These rules excludes many of numbers, so for n<1000 I've found only three primes: 5^7-1024=77101, 5^11-1024=48827101 and 634-digit one for n=907 (primality tested by Marcel Martin's Primo. Regards Wojtek (WsF) =============================================== Wojciech Florek (WsF) Adam Mickiewicz University, Faculty of Physics ul. Umultowska 85, 61-614 Poznan, Poland phone: (++48-61) 8295033 fax: (++48-61) 8295167 email: [EMAIL PROTECTED] _________________________________________________________________________ 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 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 ------------------------------ End of Mersenne Digest V1 #1097 *******************************
