Mersenne Digest Sunday, December 17 2000 Volume 01 : Number 801 ---------------------------------------------------------------------- Date: Fri, 15 Dec 2000 09:00:33 -0800 From: "Richard J. Otter" <[EMAIL PROTECTED]> Subject: Mersenne: RE: Mersenne Digest V1 #800 I haven't seen any news posted on the mersenne.org home page lately. I'm wondering about the status of the project. Are we running out of steam? I I alone in feeling a bit discouraged about finding another mersenne prime soon? Richard Otter _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Dec 2000 07:49:51 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: RE: Mersenne Digest V1 #800 On 15 Dec 00, at 9:00, Richard J. Otter wrote: > I haven't seen any news posted on the mersenne.org home page lately. > Presumably because nothing especially significant has happened? > I'm wondering about the status of the project. Are we running out of > steam? > No, judging by the rate at which completed tests are being submitted to PrimeNet :) > I I alone in feeling a bit discouraged about finding another mersenne > prime soon? Finding another prime is probably just about due on a statistical basis ... but we might or might not be lucky, it could possibly be several years before another is found. The one thing that is certain is that, if effort is withdrawn, finding that next prime will be delayed! Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Dec 2000 07:49:52 -0000 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: factoring the higher exponents On 15 Dec 00, at 10:39, Henk Stokhorst wrote: > I spend the past months factoring the range 16.000.000 up to 17.000.000 > form 2^52 up to 2^58. I reported the results once a week, which are > included in the database. This week someone else started to work on this > as well although up to 2^56. This work is therefor done twice. What is > being done and can be done to avoid this? Well, if people would stick to PrimeNet assignments, this sort of thing wouldn't happen... At least the other "culprit" is bothering to report the results, and the duplicated effort isn't too much - only about one quarter of your investment. BTW would anyone who has run P-1 on exponents in the range 100000 to 125000 (prime, with no known factors) without reporting the limits used please report them to me. I'm working through them with B1=1E6, B2=25E6 but seem not to be finding any factors - possibly someone has done them before? Regards Brian Beesley _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Dec 2000 19:15:06 -0500 (EST) From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]> Subject: Mersenne: n_th roots of 2 in a finite field? Hello. I'm putting the finishing touches on a large-integer convolution library that's optimized for the Alpha ev6, and I want to build support for Mersenne-mod convolution right into the library. However, the library is integer-only and works with integers modulo a 62-bit prime (eventually several 62-bit primes, once I code up Chinese remainder convolution). This means that in order to perform DWT arithmetic I have to find n_th roots of 2 in a finite field modulo a given prime, where n is a large power of two. I have no clue how to do this. Nick Craig-Wood's page gives some hints for the special case of 2^64-2^32+1, but not enough for me to apply the theory to other primes. It looks like you need to find primes p so that (p-1)/(order of 2 mod p) has a large power of 2 as a factor. 62-bit primes where this is the case seem quite rare; I've found only 14 primes of this size that allow a Mersenne DWT of size 2^22 or more (out of a billion candidates). But now I need some way to figure out the actual root of two. Can anybody point me in the right direction? jasonp PS: This code promises to be the fastest integer-only LL test available. It's already producing runtimes in the ballpark of floating point code, and will improve more when I add CRT code and optimize more heavily. _________________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sun, 17 Dec 2000 22:03:24 +0100 (MET) From: [EMAIL PROTECTED] Subject: Re: Mersenne: n_th roots of 2 in a finite field? If p is a prime which for which 2^22-th roots of unity exist, then p == 1 (mod 2^22). All such primes have 2 as a square, but 2 will be a 2^22 power only one time in 2^21. Of the 2^61/ln(2^61) primes between 2^61 and 2^62, only one in 2^42 will meet both requirements. You should find about 2^19/(61*ln(2)) ~= 520000/ 42 ~= 12000 cases. To test whether 2 is a 2^22-the power, check whether 2^((p-1)/2^22) == 1 (mod p). Once a p is found, you can take 22 successive square roots, starting with sqrt(2). One algorithm for sqrt(y0) mod p where y0 <> 0 picks a random nonzero x0 and tries to solve the simultaneous equations x^2 == y0 (mod p) (x + x0)^((p-1)/2) == 1 (mod p) The hope is that one of sqrt(y0) + x0 and -sqrt(y0) + x0 will be a quadratic residue, the other a non-residue. This will happen for about half of the possible x0 values (precisely those for which x0^2 - y0 is a non-residue). The left side of the degree-((p-1)/2) equation is computed modulo the quadratic x^2 - y0 (and modulo p), until one gets a linear equation ax == b (mod p). If a is nonzero, one solves for x. If a is zero, try another x0. Getting a (2^22)-th root of 1 is easier. Try x0^((p-1)/2^22) mod p, where x0 is a quadratic non-residue. Peter Montgomery > Jason Stratos Papadopoulos <[EMAIL PROTECTED]> asked Hello. I'm putting the finishing touches on a large-integer convolution library that's optimized for the Alpha ev6, and I want to build support for Mersenne-mod convolution right into the library. However, the library is integer-only and works with integers modulo a 62-bit prime (eventually several 62-bit primes, once I code up Chinese remainder convolution). This means that in order to perform DWT arithmetic I have to find n_th roots of 2 in a finite field modulo a given prime, where n is a large power of two. I have no clue how to do this. Nick Craig-Wood's page gives some hints for the special case of 2^64-2^32+1, but not enough for me to apply the theory to other primes. It looks like you need to find primes p so that (p-1)/(order of 2 mod p) has a large power of 2 as a factor. 62-bit primes where this is the case seem quite rare; I've found only 14 primes of this size that allow a Mersenne DWT of size 2^22 or more (out of a billion candidates). But now I need some way to figure out the actual root of two. Can anybody point me in the right direction? jasonp PS: This code promises to be the fastest integer-only LL test available. It's already producing runtimes in the ballpark of floating point code, and will improve more when I add CRT code and optimize more heavily. _________________________________________________________________________ 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 ------------------------------ End of Mersenne Digest V1 #801 ******************************
