Mersenne: Wow...
HTTP Error 403 403.9 Access Forbidden: Too many users are connected This error can be caused if the Web server is busy and cannot process your request due to heavy traffic. Please try to connect again later. Please contact the Web server's administrator if the problem persists. Sounds like M38 gave www.mersenne.org some extra traffic? /* Steinar */ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Head's algorithm for multiplying mod n
All, In the book _Primes and Programming_ Head's method of multiplying two numbers mod n is mentioned. Is this actually more effiecient than simply multiplying the two numbers and taking the modulus? If so, is it implemented in the various mersenne factoring programs in use? Thankyou, Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Publicity from the 38th
At 06:59 08.07.99 -0400, Lucas Wiman wrote: I think that we should put the publicity from the 38th mersenne prime to good use. If we all write letters to the local paper, then we can probably gain a very large number of people. Stick encouragements to join on your website, in you .sig files, anywhere you can think of. Be sure to mention the prize money involved in the finding of the 38th. This should speed us on our way to victory... Not to mention advertising Prime95 v19 when it comes (think software sites: Tucows/Linuxberg, Freshmeat (for mprime), etc.). Especially in the Linux world, Freshmeat will make people _know_ about GIMPS. /* Steinar */ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Publicity from the 38th
all, I think that we should put the publicity from the 38th mersenne prime to good use. If we all write letters to the local paper, then we can probably gain a very large number of people. Stick encouragements to join on your website, in you .sig files, anywhere you can think of. Be sure to mention the prize money involved in the finding of the 38th. This should speed us on our way to victory... -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Status question
If you run prime there is under test and status a number that gives the change to find a prime. On which base is this number calculated? bye Paul van Grieken Alcatel Telecom Nederland afd: T-TAC NE Kamer:4121 Postbus 3292 2280GG rijswijk Nederland Phone: + 31 70 307 9353 Fax: + 31 70 307 9476 Email: [EMAIL PROTECTED] Prive: Ruys de Beerenbrouckstraat 1 2613AS Delft Netherlands Marklin collector Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Head's algorithm for multiplying mod n
At 06:19 AM 7/8/99 -0400, you wrote: All, In the book _Primes and Programming_ Head's method of multiplying two numbers mod n is mentioned. Is this actually more effiecient than simply multiplying the two numbers and taking the modulus? Yes, because it keeps the numbers smaller. It was originally: Method from Multiplication Modulo N, by A. K. Head, Bit 20 (1980) 115-116 +--+ | Jud "program first and think later" McCranie | +--+ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: M38 = M6972593
NOW it does, after the official announcement Remember when Roland found M37? Someone found a 0x000 residue in the report and beat George to the punch, so Scott modified the reports so that they would NOT post a zero residue automatically. So THIS time, when word came that we'd found a potential prime, some enterprising person immediately grabbed the "assigned exponents" file, and the "cleared exponents" file, and by the process of elimination, deduced the prime number because it was the ONLY candidate listed as "assigned" but was not EITHER cleared as non-prime or still in progress. Actually, it was updated and added on July 5. Previously, the cleared exponent list looked like the following (accounts removed for space): 6972451 62 0x1921D245846367__25-Jun-99 15:07 6972467 62 0x01123F0756E444__03-Jul-99 11:27 6972509 62 0x681B51793464A4__17-May-99 06:07 6972617 62 0xC377193C8903C1__05-Apr-99 05:25 6972649 62 0x30982ED7214ACA__09-May-99 12:49 6972709 62 0xEADF232189A0F0__21-Jun-99 08:30 George was telling Scott to correct for this 'leak' so that a really determined person could not do a comparison-elimination to deduce a prime number find before George announces it. Fixing this one 'leak' won't do the job, if you know how and where to look... Besides, *some people* know how to keep quiet about certain things. You didn't see this person going around announcing it to the world immediately after it was found, did you??? In fact, their website didn't post it being found until after it was verified, and even then, didn't disclose the number!! On the other hand, they could've noticed a discrepany and shrugged it off as meaningless until after word got out a new prime was found. At that point, they could've gone back and said to themselves '*that explains the discrepany!*'. Just a couple of possibilities Of course, Curt Noll's web page made that a pointless exercise... ;-) (Note to Scott - create a dummy non-zero residue a stick it in the cleared exponents report). Too late!! The Cleared Exponents Report reads: 6972593 62 P 0x 01-Jun-99 13:57 nayan precision-mm Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Lehmer question
Peter-Lawrence.Montgomery wrote: Problem A3 in Richard Guy's `Unsolved Problems in Number Theory' includes this question, by D.H. Lehmer: Let Mp = 2^p - 1 be a Mersenne prime, where p 2. Denote S[1] = 4 and S[k+1] = S[k]^2 - 2 for k = 1. Then S[p-2] == +- 2^((p+1)/2) mod Mp. Predict which congruence occurs. Of course, the reason that S[p-2] == +- 2^((p+1)/2) mod Mp is that we know that S[p-1] == 0 mod Mp, and S[p-1] = S[p-2]^2 - 2, thus S[p-2] is a square root of 2 mod Mp. Then since 2^p == 1 mod Mp, 2^(p+1) == 2 mod Mp, thus +- 2^((p+1)/2) are the square roots of 2 mod Mp, and S[p-2] must be congruent to one of these mod Mp. I don't see any easy way of predicting the sign, but the following might be helpful. We know that it is possible to use a value other than 4 for S[1] in the LL sequence, e.g. we can set S[1] = 10 instead. Suppose that b is such that if we set S[1] = b, then S[p-1] == 0 mod Mp. The necessary and sufficient condition that b have this property is that b-2 is a quadratic residue mod Mp and b+2 is a quadratic nonresidue mod Mp. It turns out that there are exactly 2^(p-2) = (Mp+1)/4 values b which have this property, and there is a systematic way of generating them. Let L[0] = 2, L[1] = 4, L[j+2] = 4*L[j+1] - L[j]. (The sequence L[j] is related to the sequence S[k] with S[1] = 4 by the following identity: S[k] = L[2^(k-1)].) Let B[j] = L[2*j-1] for j = 1..2^(p-2). Then the values B[j] mod Mp are all distinct, and each B[j] has the desired property. Of this set B[j], exactly half correspond to S[p-2] == +2^((p+1)/2) mod Mp, and the other half correspond to S[p-2] == -2^((p+1)/2) mod Mp. The two subsets are the set B1[j] = B[j] for j = 0,1,4,5 mod 8, and the set B2[j] = B[j] for j = 2,3,6,7 mod 8. 4, which is B[1], belongs to B1. I do not know which of the sets B1 and B2 corresponds to the + sign for S[p-2]. Note that B[2] = 52 belongs to B2, thus the sequences beginning with S[1] = 4 and S[1] = 52 have opposite signs for S[p-2]. The above, with a few modifications, also works for primes of the form c*2^n - 1, where c 1 is odd and n is not necessarily prime. Suppose that q = c*2^n - 1 is prime. Let b be such that b-2 is a quadratic residue mod q and b+2 is a quadratic nonresidue mod q. Let L[0] = 2, L[1] = b, L[j+2] = b*L[j+1] - L[j]. Let B[j] = L[c*(2*j-1)] for j = 1..2^(n-2). Let S[1] = B[j], S[k+1] = S[k]^2 - 2. Then S[p-1] == 0 mod q, and S[p-2] is a square root of 2 mod q. Exactly half of the B[j] correspond to a specific value of S[p-2]. The subsets B1 and B2 can be defined in the same way as for the case c = 1. Regards, Bill ** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. This footnote also confirms that this email message has been swept by MIMEsweeper for the presence of computer viruses. ** Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Wow...
On 8 Jul 99, at 9:51, Steinar H. Gunderson wrote: HTTP Error 403 403.9 Access Forbidden: Too many users are connected Sounds like M38 gave www.mersenne.org some extra traffic? This problem has been around for a few days. The other explanation is that the server has lost some TCP buffers due to a driver bug or a denial-of-service attack. Such things are known 8-( My FTP server has been unusually active this week (or, rather, unusually not inactive!), in particular there seems to be a surge of interest from Poland, with quite a number of people downloading prime95.zip 8-) Regards Brian Beesley Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Infinitude of Sophie-Germains]
Hello List: I might be jumping the gun in here (as I have not read yet all the Mersenne Digest #574. ) However. These are called Sophie Germain primes, and it has been proven that there are an infinite number of them, Source:[EMAIL PROTECTED] AND I'm not sure whether or not it has been proven whether or not there are an infinity of Sophie Germain primes of the form 4*n+3. I imagine there would be, as there are an infinity of primes in the form 4*n+1 and 4*n+3. Source:[EMAIL PROTECTED] stuck to me like a sore thumb. I am not aware that anyone has yet proven the infinitude of Sophie Germain Primes. [Granted that, in itself, does not mean anything ;) ] I am aware of the Hardy-Littlewood conjectures that not only (if proven) indicate that there are infinite SG Primes but would also give an approximation as to their frequency (and that info is available on Professor's Caldwell Prime Pages) but at least until the publication of Paulo Ribenboim, "The New Book of Prime Number Records," Springer Verlag, New York, 1st Ed. -i.e. 1995- this (infinitude of Sophie Germains and/or infinitude of composite Mersenne Numbers) had _not_ been proven. I'm also familiar with Lejeune Dirchlelet demonstration in 1826 of the fact that there are infinite number of primes in any arithmetical progression with the first term coprime to the difference. Thus, the infinitude of primes of the forms 4n+3 and 4n+1 is a corollary of this proof. So, if anyone of the correspondents (or any other member of the list for that matter) would be so kind as to refer me to the publication (or Web Page) in which this proof has been announced, I would be eternally grateful. Now, as a disclaimer, I am speaking about "mathematical proof' on the Godfrey H. Hardy tradition, and not merely heuristical approaches. Thanks, Rodolfo Ruiz Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Publicity from the 38th
Actually I think mentioning the prize money might constitute deception, since the next prize isn't in reach, yet. However, I agree with your sentiment, except - _what_ "victory"? It might be interpreted as a deception, I suppose... "victory" would of course be finding another prime... -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
RE: Mersenne: Publicity from the 38th
From: Lucas Wiman However, I agree with your sentiment, except - _what_ "victory"? It might be interpreted as a deception, I suppose... "victory" would of course be finding another prime... To me [read: disclaimer], 'victory' implies a successful end. Perhaps 'success' would get the idea across? Rick. - [EMAIL PROTECTED] http://www.alienshore.com/ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Infinitude of Sophie-Germains]
At 11:52 AM 7/8/99 -0700, Rudy Ruiz wrote: I am not aware that anyone has yet proven the infinitude of Sophie Germain Primes. [Granted that, in itself, does not mean anything ;) I was wrong. As far as I know, it hasn't been proven either (but it is almost certainly true). I had seen a conjectured distribution function that went to infinity, but it has not been proven. +--+ | Jud "program first and think later" McCranie | +--+ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Head's algorithm for multiplying mod n
On Thu, 08 Jul 1999, Brian J. Beesley wrote: On 8 Jul 99, at 6:19, Lucas Wiman wrote: In the book _Primes and Programming_ Head's method of multiplying two numbers mod n is mentioned. Is this actually more effiecient than simply multiplying the two numbers and taking the modulus? Look at it this way. Head's method is essentially binary long multiplication, with the "wrinkle" that you take the remainder modulo n after each shift add operation. That is going to be a *lot* slower than FFT convolution, for numbers the size of the Mersenne numbers we're testing! FFT is O(n*log(n)) where n is the number of limbs in the numbers being multiplied. Head's method is O(n^2), with O being slightly smaller than for straight long multiplication. A recursive method splitting the number in the middle, then doing a subtraction trick to make three instead of four submultiplies, is O(n^y), where y is log(3)/log(2), which is about 19/12. phma Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Head's algorithm for multiplying mod n
At 08:11 PM 7/8/99 -0400, Pierre Abbat wrote: That is going to be a *lot* slower than FFT convolution, for numbers the size of the Mersenne numbers we're testing! Head's algorithm is for getting x*y mod n when 0=x,yn; and n is such that nM but n^2M, where M is the largest integer you can store in a format native to the computer. I don't think it applies for Mersenne testing, but it helps a lot with Fermat-type tests (pseudoprimes, etc). +--+ | Jud "program first and think later" McCranie | +--+ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Head's algorithm for multiplying mod n
Hi folks In the book _Primes and Programming_ Head's method of multiplying two numbers mod n is mentioned. Is this actually more effiecient than simply multiplying the two numbers and taking the modulus? Look at it this way. Head's method is essentially binary long multiplication, with the "wrinkle" that you take the remainder modulo n after each shift add operation. That is going to be a *lot* slower than FFT convolution, for numbers the size of the Mersenne numbers we're testing! FFT is O(n*log(n)) where n is the number of limbs in the numbers being multiplied. Limbs? It is good to know that the world has many different literal meanings in many languages for "bits" - variety is good for us all. (The French word for "buffer" is also, I seem to remember, rather amusing). But enough already. One thing I'm surprised nobody has mentioned yet - is it even in Lucas' FAQ? - is that modular reduction in the Mersenne case is sinfully inexpensive. Even with a pure integer, no FFT implementation, reduction mod 2^p-1 is very quick - take the lower p bits, take the rest of the number shifted down by p bits, add them together. The size of the original number is usually around 2p bits, so one iteration of the shift-and-add will get the result correct to within 1 extra subtraction at most. As for the FFT implementation, modular reduction is less than inexpensive - it is virtually free - in fact, it makes use of a fact that means the algorithm can be a large factor faster than "arbitrary" arithmetic in the Mersenne case. In a standard FFT multiplication, the numbers have to be buffered with a large "dead zone" of zeroes - this is due to the fact that the FFT algorithm works with a periodic signal, so data bits "wrap around" from either end unless you have a large enough zero-buffer. The Mersenne method uses it to it's advantage - the bits 2^p and above *should* wrap onto the least-significant bits as part of the modular reduction. With a little adjustment (using a non-rational arithmetic base so 2^p is in fact a power of 2 power of the base), the modular reduction then becomes a desirable, and free, side-effect of the multiply algorithm - not to mention, the FFT buffer is half as large, and so calculations are implicitly faster. Chris Nash Lexington KY UNITED STATES = Still a co-discoverer of the largest known *non*-Mersenne prime. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Head's algorithm for multiplying mod n
Limbs? It is good to know that the world has many different literal meanings in many languages for "bits" - variety is good for us all. (The French word for "buffer" is also, I seem to remember, rather amusing). "Limb" is the term used in gmp for a digit in a large base (such as 2147483648) in which a number is represented in a multiple-precision package. phma Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Head's algorithm for multiplying mod n
Pierre Abbat writes: In the book _Primes and Programming_ Head's method of multiplying two numbers mod n is mentioned. Is this actually more efficient than simply multiplying the two numbers and taking the modulus? Look at it this way. Head's method is essentially binary long multiplication, with the "wrinkle" that you take the remainder modulo n after each shift add operation. That is going to be a *lot* slower than FFT convolution, for numbers the size of the Mersenne numbers we're testing! FFT is O(n*log(n)) where n is the number of limbs in the numbers being multiplied. Head's method is O(n^2), with O being slightly smaller than for straight long multiplication. A recursive method splitting the number in the middle, then doing a subtraction trick to make three instead of four submultiplies, is O(n^y), where y is log(3)/log(2), which is about 19/12. Well, I wasn't talking about the massive scale of numbers used in LL tests. I was speaking of the 95 bit integers used in factoring, and using Head's algorithm in the calculation of 2^p mod f. I doubt that FFT would be worthwhile here, and would probably slow it down considerably. Chris Nash writes: But enough already. One thing I'm surprised nobody has mentioned yet - is it even in Lucas' FAQ? - is that modular reduction in the Mersenne case is sinfully inexpensive. Even with a pure integer, no FFT implementation, reduction mod 2^p-1 is very quick - take the lower p bits, take the rest of the number shifted down by p bits, add them together. The size of the original number is usually around 2p bits, so one iteration of the shift-and-add will get the result correct to within 1 extra subtraction at most. I think I might split off the parts about modular arithmetic into their own section, or in the beginning stuff section. I'll probably add this question sometime tomorrow. -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
