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
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
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
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,yM, 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
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: Mersenne M38
>Actually, now that the exponent for M38 is known, I can say >that I had narrowed it down to 5 candidates (7 before the >Oregonian article). They were: >5,750,881 6,382,513 6,836,327 6,972,593 >7,143,163 7,213,391 7,310,981 George's original message said it was in the 6,000,000s so that would limit it to three candidates. If you noticed that the only range in the "Mersenne Exponent Test Distribution Map" that didn't agree (it said there was one more) with with the cleared exponents list was the range 6,900,000 - 7,000,000 then that would have limited it to one exponent. Herb Savage >These were the only exponents that were no longer being >worked on in one form or another, and was not listed on the >cleared exponents list, for that time frame... Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: M38 = M6972593
At 08:25 AM 7/8/99 -0700, Eric Hahn wrote: >Fixing this one 'leak' won't do the job, if you know how >and where to look... It would have stopped me. >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!! I wonder whose "their website" is? >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!*'. Nope, I didn't start looking at the various files until George had posted his message. Herb Savage Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Infinitude of Sophie Germains]
To: Jud McCranie <[EMAIL PROTECTED]> Thanks.. I have read some of the mail that followed the ones I quoted and seen that you corrected that. Sincerely speaking I would have preferred you to be right and me to be wrong. I believe that "proofs are neat things"(tm) and would have jumped to the place where it was announced, in no time... R R Jud McCranie wrote: >. 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: 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: 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: 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: Head's algorithm for multiplying mod n
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. The remaindering operation here is very simple, as all you have to do is to subtract n if the result >= n. Nevertheless you're into a _lot_ of operations, involving badly- aligned data (which means doing lots of multi-precision shifts - which are slow because of dependency chains - also the "subtract n if >= n" is slow because the branch is hard to predict). Conversely, multiplying the whole number out & then taking the modulus once _may_ be inefficient, because you will probably be forced out of registers & have to do a lot of operations in memory. My factoring code compromises. It does long multiplication 32 bits at a time, creating a 128-bit product from a 96-bit by 32-bit multiplication operation, then reduces this modulo n leaving a result with at most 95 significant bits. The shifts involved are 32-bit shifts i.e. an address offset costing no CPU time. I _do_ have to reduce modulo n 3 times, but the multiplications actually dominate the time, and I can get away with using only the limited registers in the x86 processor plus four cache lines worth of memory (including storage for factor, remainder, etc.). I suppose you could call this a variant of Head's method ... note that I get only 95 bits from a 96 bit field in the same way that Head gets only (n-1) bits from an n bit field, you lose one bit precision because you have to add together the partial results of the multiplication after taking the modulus. Nevertheless Head's method is useful, especially if you're working in a language like Java that has limited support for multiprecision arithmetic, since it allows you to do arithmetic modulo n for n up to 2^30 even if you have only 32-bit signed arithmetic available. There are more time-saving tricks employed, like "early exit" from the whole stage when a partial multiplier is zero, and saving the partial products thereby reducing the number of 32-bit by 32-bit multiplies required from 9 to 6. > > If so, is it implemented in the various mersenne factoring programs > in use? I caught onto this idea when I was trying to do 2^p mod f as fast as possible for 2^64 < f < 2^80 - and got the extension to 2^95 "for free". I found it to be 10% - 20% faster than multiplying out the whole product (i.e. calculating x^2) then taking the modulus, and at least 10 times as fast as a straightforward implementation of Head's method. It will probably not be optimal for other size factors or for other processor architectures. I did, however, find that I got the best performance doing the job this way on Intel Pentium / PPro type CPUs for factors a little larger than 2^64 - which was the task briefed. 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: 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
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: 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: 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
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, 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? No it is actually much less efficient, but you are missing the point. In his book Peter Giblin explains why on P93. Essentially if a and b are say 62-bit integers, to compute a * b (mod m) you generate intermediate values that are up to 124-bits long which are not generally supported in Basic/Pascal/C/C++. One would have to resort to Ubasic or a Large Integer Package. The beauty of Head's algorithm is that it allows you to compute the modular product using only or two extra bits. The example in the book would allow you to compute the modular product of two 62-bit integers without intermediate values exceeding 64-bits. As far as I know most Mersenne factoring programs use on some form of Large Integer Package (LIP) to handle the size of numbers involved. Regards Alan Powell 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
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: 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
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
