Mersenne Digest Friday, July 16 1999 Volume 01 : Number 598 ---------------------------------------------------------------------- Date: Wed, 14 Jul 1999 14:48:37 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Benford's Law (was: re: Mersenne prime exponent binary) On 13 Jul 99, at 13:41, Todd Sauke wrote, in reply to my previous message > Brian Beesley wrote: > > >Actually we should expect an excess of smaller leading digits over > >that predicted by "Benford's Law" in this case. A smaller exponent is > >more likely to be prime than a larger exponent, and a smaller prime > >exponent is more likely to give rise a Mersenne prime than a larger > >prime exponent. "Benford's Law" would follow if _every_ exponent > >(prime or composite) was equally likely to give rise to a Mersenne > >prime. > > > > This is not true. Actually, it is the fact that smaller primes are more > likely to give Mersennes that theoretically should result in a "Benford's > Law" type behavior of the second leading bit. It is in some sense an > "accident" that Mersenne exponents SHOULD follow Benford's Law (at least > the second bit generalization of it), and an irony that, due to small > number statistics, they actually DON'T! (68% zeroes instead of predicted > 58% or whatever) The effect I was predicting was small. Experiments indicate it should be hard to detect, even with the small numbers of Mersenne primes known. The relevant fact is that we have reasonable coverage of exponents up to approx. 5 million, not that we know less than 40 Mersenne primes. > Benford's Law comes about because of power law scaling of > some numbers. Many of the referenced web links emphasized that Benford's > law is NOT for "regular" numbers, but ONLY for numbers expressing amounts > in some (human selected) units, and that it is some property of "power law > scaling" and/or "logarithmic invariance" of arbitrary choice of units to > express AMOUNTS (NOT numbers) of things that result in Benford's law. > There is an article on this phenomenon in the current on-line issue of "New Scientist" (UK), the URL is http://www.newscientist.com/ns/19990710/thepowerof.html Regards Brian Beesley ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 14 Jul 1999 15:03:07 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Hyperbola On 14 Jul 99, at 1:26, Paul Leyland wrote: > Fermat observed that if one could represent an integer as the difference of > two squares, its factorization would be at hand; he then gave an efficient > (for the 17th Century!) algorithm for finding the squares. > > More recently, algorithms such Continued Fraction, Quadratic Sieve and > Number Field Sieve have all used Fermat's idea in the form x^2-y^2 = kN (k a > small integer) or, equivalently, x^2 == y^2 (mod N) to factor N. The > algorithms differ in how they construct the x and y and are *much* more > efficient than Fermat's algorithm, but the underlying idea is the same. > Actually Fermat's Method is extraordinarily efficient at finding a factorization n = a * b when (a - b) is small. It's also easy to code, needs very little storage and (once initialized) requires only relatively low-precision arithmetic, therefore making the attempt fast (per iteration). This is one reason why it's a Very Bad Idea to use the product of a pair of primes of similar size as a public key. In fact, Fermat's Method will factorize the product of a pair of twin primes almost instantaneously, irrespective of their size! Just out of interest, did anyone ever try Fermat's Method on some of the "tougher" numbers in the Cunningham tables ... Fermat's Method can be speeded up by a large factor since we _know_ the form of the factors - of course, it's still going to fail to find factors in a reasonable time unless a pair of factors of very similar size do, in fact, exist. Also, any factors found would not neccessarily be prime, though cracking the two "halves" ought to be easier than tackling the whole. Regards Brian Beesley ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 14 Jul 1999 16:58:41 +0200 (MET DST) From: [EMAIL PROTECTED] Subject: RE: Mersenne: Hyperbola Brian Beesley comments: > Just out of interest, did anyone ever try Fermat's Method on some of > the "tougher" numbers in the Cunningham tables ... Fermat's Method > can be speeded up by a large factor since we _know_ the form of the > factors - of course, it's still going to fail to find factors in a > reasonable time unless a pair of factors of very similar size do, in > fact, exist. Also, any factors found would not neccessarily be prime, > though cracking the two "halves" ought to be easier than tackling the > whole. D.H. Lehmer did some cofactors this way. The largest seems to be the 33-digit number (2^109 - 2^55 + 1)/5, otherwise known as 2,218L. See the history pages in the book `Factorizations of b^n +- 1, b = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers' by John Brilhart et al. The Continued Fraction method, introduced in the late 1960's, generalized Fermat's method and made the difference of squares method obsolete. The P-1 method accelerated this gap. Today it takes under a second to factor 2,218L by P-1. Montgomery factorization program. Compiled Tue Jun 3 21:25:54 MET DST 1997. Allows inputs up to about 6300 decimal digits. C(2,218L) Composite cofactor has 33 digits: 129807421463370683507503004437709 RAND_PRINT - Current random number seed is 198181203 271851921 233382925 C(2,218L) p-1 method found divisor near p= 7603 74323515777853 CHEK - Nontrivial GCD p-1 74323515777853 The first number below is the product of the second and the third, as found by p-1 after 18285 multiplies and GCDs in 0.05 CP seconds at Wed Jul 14 16:52:44 1999 129807421463370683507503004437709 74323515777853 1746518852140345553 Probable prime cofactor has 19 digits -- terminating. One instance of Fermat's method remains important -- factoring p^2 where p is prime. Peter Montgomery ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 14 Jul 1999 07:59:23 -0700 From: Paul Leyland <[EMAIL PROTECTED]> Subject: RE: Mersenne: Hyperbola > From: Brian J. Beesley [mailto:[EMAIL PROTECTED]] > On 14 Jul 99, at 1:26, Paul Leyland wrote: > > > Fermat observed that if one could represent an integer as the difference of > > two squares, its factorization would be at hand; he then gave an efficient > > (for the 17th Century!) algorithm for finding the squares. > > > > More recently, algorithms such Continued Fraction, Quadratic Sieve and > > Number Field Sieve have all used Fermat's idea in the form x^2-y^2 = kN (k a > > small integer) or, equivalently, x^2 == y^2 (mod N) to factor N. The > > algorithms differ in how they construct the x and y and are *much* more > > efficient than Fermat's algorithm, but the underlying idea is the same. > > > Actually Fermat's Method is extraordinarily efficient at finding a > factorization n = a * b when (a - b) is small. It's also easy to > code, needs very little storage and (once initialized) requires only > relatively low-precision arithmetic, therefore making the attempt > fast (per iteration). All of this is completely true, as long as the concept "small" is well understood. Fermat's method is excellent if (a-b) is about sqrt(a) or sqrt(sqrt(N)). If it is much larger than this, Fermat's method is hopelessly slow. In a "typical case", Fermat's method is slower than trial division! "Typical" needs careful definition, of course. I won't go into the assumptions and derivations, but in a "typical" integer, successive factors (in numerical order) are about twice the length of their predecessors. This means that (a-b) is far from "small". A more rigorous formulation of this behaviour can be found in standard texts, such as Knuth's Art of Computer Programming, Vol II. > This is one reason why it's a Very Bad Idea to use the product of a > pair of primes of similar size as a public key. In fact, Fermat's > Method will factorize the product of a pair of twin primes almost > instantaneously, irrespective of their size! Indeed, if "similar" is interpreted as is "small" above. In a typical case, a 512-bit key, the two primes will have about 78 digits each. They have to be identical to the first 35-ish digits to be "similar". If the primes are chosen randomly, the random number generator has to be truly dreadful for that to happen by chance. > Just out of interest, did anyone ever try Fermat's Method on some of > the "tougher" numbers in the Cunningham tables ... Fermat's Method > can be speeded up by a large factor since we _know_ the form of the > factors - of course, it's still going to fail to find factors in a > reasonable time unless a pair of factors of very similar size do, in > fact, exist. Also, any factors found would not neccessarily be prime, > though cracking the two "halves" ought to be easier than tackling the > whole. Not as far as I know, though some "similar" factors are known from algebraic considerations. These are known as Aurifeuillean factorizations. A simple example is 2^{2h} + 1 = (2^h-2^k+1) * (2^h+2^k+1) where h = 2k-1. Paul ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 14 Jul 1999 09:28:08 -0700 From: "John R Pierce" <[EMAIL PROTECTED]> Subject: Mersenne: phew Geez, just noticed my newest processor (a 2nd P2-400 added to a dual CPU mobo) got 3 LL exponents in the 7,993,000 range. 8 million is right around the corner, phew. So how far before we hit 64 bit and *really* get nailed for speed?? prime fact days exponent bits run / to go / exp date updated - -------- ---- ----------------- --------------- 7993057 63 1.8 25.0 61.0 13-Jul-99 15:33 7993093 63 1.8 51.0 61.0 13-Jul-99 15:33 7993099 63 1.8 78.0 61.0 13-Jul-99 15:33 ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 14 Jul 1999 23:55:40 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Development of Fermat's Method (was: RE: Mersenne: Hyperbola) On 14 Jul 99, at 7:59, Paul Leyland wrote, in reply to my earlier message: > > Actually Fermat's Method is extraordinarily efficient at finding a > > factorization n = a * b when (a - b) is small. It's also easy to > > code, needs very little storage and (once initialized) requires only > > relatively low-precision arithmetic, therefore making the attempt > > fast (per iteration). > > All of this is completely true, as long as the concept "small" is well > understood. > > Fermat's method is excellent if (a-b) is about sqrt(a) or > sqrt(sqrt(N)). If it is much larger than this, Fermat's method is > hopelessly slow. In a "typical case", Fermat's method is slower than > trial division! I think you mean we want (a-b) to be _much_ smaller than sqrt(a) if Fermat's method is going to succeed reasonably quickly. However, ... Suppose we take a number which is proving troublesome to factorize, e.g. 2^727-1. Factors of this number are going to be of the form 1454k+1. The number is 219 decimal digits long; we are fairly sure, from work expended in ECM, that there are no factors much less than 45 digits long. Suppose we multiply 2^727-1 by 100!. The reason for doing this is that this just about guarantees that there is some combination of factors a, b such that (a-b) << sqrt(a). Therefore we should be able to use Fermat's method (or anything else which might be better) and get a factorization in a reasonable time. We also know that none the factors of 2^727-1 are < 100, so we can then reduce the factors found by dividing out of them all the primes < 100. What we're left with must surely be the factorization of 2^727-1 (though the remaining factors might possibly still be composite). Now I'm not saying that the effort involved is trivial - I'm sure a run length of some hours, days or weeks would be neccessary. Also, I'd be very surprised indeed if I'm the first to suggest a trick like this, but, is it worth while starting to code this method? The point is that it's going to take a fair number of CPU years to complete ECM testing on 2^727-1 to the point where we're reasonably sure that there are no factors < 10^50; for all we know, there might be only 2 factors each over 100 digits long, in which case ECM is almost certain to fail, unless _much_ faster hardware comes along. Regards Brian Beesley ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 14 Jul 1999 21:22:26 -0400 From: Chris Nash <[EMAIL PROTECTED]> Subject: Re: Development of Fermat's Method (was: RE: Mersenne: Hyperbola) Hi folks > Suppose we take a number which is proving troublesome to factorize, > e.g. 2^727-1. Factors of this number are going to be of the form > 1454k+1. > Suppose we multiply 2^727-1 by 100!. The reason for doing this is > that this just about guarantees that there is some combination of > factors a, b such that (a-b) << sqrt(a) > Now I'm not saying that the effort involved is trivial - I'm sure a > run length of some hours, days or weeks would be neccessary. Also, > I'd be very surprised indeed if I'm the first to suggest a trick like > this, but, is it worth while starting to code this method? I can give a reasonably informed answer to this, having tried it myself. To use Fermat's method directly on kN in order to factor N, unless you are very lucky, is no improvement. In the 2^727-1 case, as pointed out, since you know the form of the factors, it's sufficient to try a=727x+1, for all a above sqrt(N), to check a^2-N is a perfect square. To preserve this, make the factor you multiply by a product of factors of the form 1454k+1 - all the factors of the product are still of this form. Do we win, or do we lose? Let's suppose that our composite has precisely two prime factors, and thus direct application of Fermat will uncover only one non-trivial solution from which we can derive the factor values. If what we multiply by has k distinct factors, then there are now 2^k useful solutions - but the number of values of a that we need to try has increased by more than that factor. In all likelihood, it would take longer... But don't despair. Since all we have to check for is "a^2-N is a perfect square", it's easy just to inspect this value modulo many small primes and sieve out quadratic non-residues. With a few lookup tables, it's easy to trial-factor at 10^9, even 10^12, values of a per CPU-second. Even so, for a 219-digit number like 2^727-1, and even assuming there's no factor below 40 or so digits, you'd still need 10^60 or more CPU-seconds to spare. (OK if you've got a universe with nothing else to do). Unsurprisingly, the method needs a bit of control to be realizable - which is what the continued fraction method achieves. Each iteration finds a (relatively) small square modulo N (at worst sqrt(N) in absolute value), which, after striking out square factors, making sensible choices of which to store, and judicious combinations, you hope to eventually find non-trivial a^2=b^2 mod N. Still need a lot of luck, though, and the steps are now non-trivial... 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 ------------------------------ Date: Wed, 14 Jul 1999 18:48:51 -0700 From: Todd Sauke <[EMAIL PROTECTED]> Subject: Re: Development of Fermat's Method (was: RE: Mersenne: Hyperbola) Brian Beesley wrote: >Suppose we multiply 2^727-1 by 100!. The reason for doing this is >that this just about guarantees that there is some combination of >factors a, b such that (a-b) << sqrt(a). Therefore we should be able >to use Fermat's method (or anything else which might be better) and >get a factorization in a reasonable time. But the guarantee is not there. your a ~ sqrt(2^727 * 100!) ~ 10^188 sqrt(a) ~ 10^94 There are (only) 2^100 ~ 10^30 ways to choose the combinations of factors of 100! , which are the degrees of freedom. But they need to be chosen so that a-b << 10^94 for a (and b) near 10^188. For f1, a factor of 2^727-1, near 10^100 it will be nearly impossible (not guaranteed) for (f1 * some combination of the factors of 100!) to be within one part in 10^94 of a certain number ~10^188. The combination of factors of 100! need to be within 10^-6 of a certain number of size ~ 10^88. 10^30 chances at hitting a number ~10^88 to within 10^-6 leaves you several dozen orders of magnitude short of a guarantee. Best regards, Todd Sauke ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 14 Jul 1999 20:11:39 -0700 From: "John R Pierce" <[EMAIL PROTECTED]> Subject: Re: Mersenne: phew Steinar H. Gunderson <[EMAIL PROTECTED]> replies to me... > On Wed, Jul 14, 1999 at 09:28:08AM -0700, John R Pierce wrote: > >So how far before we hit 64 bit and *really* get nailed for speed?? > > You mean 64 bits of optimal factoring? Unless George comes up with > something very smart (ie. a new factoring algorithm), I guess we > will be stuck with 64 bits as optimal for a while, I'm afraid :-( Well, the current range of Mp candidate values (just under 8,000,000) is described as using a 63 bit 'factor'... I would assume eventually this has to go to 64 bits, but I'm not clear on the relationship between the exponent and the FFT size and the 'fact bits' listed on the test status pages. - -jrp ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Wed, 14 Jul 1999 23:26:29 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Mersenne: subtracting 2: error in FAQ All, I recieved a message pointing out a possible error in my FAQ: > Speaking of Q2.6, I've heard that with Crandall's DWT, the subtraction > 2 step costs nothing at all. It's done automatically within the > transformation. Try checking this with George Woltman. Is this true? - -Lucas ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 15 Jul 1999 03:44:43 +0000 (GMT) From: Kris Garrett <[EMAIL PROTECTED]> Subject: [none] Could someone show me a proof for(if there is one): The number 2^p-1 has factors in the form of 2pk+1 where k is any positive integer. _________________________________________________________ Do You Yahoo!? Get your free @yahoo.com address at http://mail.yahoo.com ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 15 Jul 1999 00:52:34 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Proof of factor forms > Could someone show me a proof for(if there is one): > The number 2^p-1 has factors in the form of 2pk+1 > where k is any positive integer. try http://www.utm.edu/research/primes/notes/proofs/MerDiv.html - -Lucas ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 15 Jul 1999 11:42:45 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Re: Mersenne: subtracting 2: error in FAQ (?) At 23:26 14.07.99 -0400, Lucas Wiman wrote: >> Speaking of Q2.6, I've heard that with Crandall's DWT, the subtraction >> 2 step costs nothing at all. It's done automatically within the >> transformation. Try checking this with George Woltman. >Is this true? Not knowing for certain; I thought the DWT did the modulo for you, not the subtraction? /* Steinar */ ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Thu, 15 Jul 1999 06:03:08 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: subtracting 2: error in FAQ (?) >>> Speaking of Q2.6, I've heard that with Crandall's DWT, the subtraction >>> 2 step costs nothing at all. It's done automatically within the >>> transformation. Try checking this with George Woltman. >>Is this true? >Not knowing for certain; I thought the DWT did the modulo for you, not the >subtraction? Yes, it does the mod. I read in the archives that x^2-2 could be interpreted as a "delta polynomial" which would give it a valid Fourier transform. I was wondering if this was what was actually performed. I doubt it is as optimizing the -2 step would hardly produce amazing results. Optimizing the -2 step down to nothing (with the amazingly high estimate of 1/50,000th of a sec) would gain only .3 CPU years for all exponents in the 7million range. I was just making sure. - -Lucas Wiman ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Fri, 16 Jul 1999 00:42:50 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Mersenne: ECPP for intel (linux) Does anyone know where I can obtain a copy of ECPP for the intel platform, specifcally Linux? I apologize for the slightly off topic-ness of this question... thank you, Lucas Wiman ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Fri, 16 Jul 1999 05:57:38 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Mersenne: Adding FFT to the FAQ All, I tried to add an FFT section to the FAQ, and here is what I got: (please add, or correct errors...) - -Lucas Wiman P.S. Sorry if the FAQ is causing more traffic than it is supposed to prevent ;) =========================================================================== Q6.1: How can we perform the massive squarings required for the LL test in reasonable time? A: We use a method known as FFT convolution. In this method, we take the number that we are squaring, and run an FFT on it. This results in an array, and we square each element in that array, and run an IFFT (iverse-FFT). This yields the answer mod some number. This operates in O(n*log(n)) time, which means that it is proportional to n*log(n). This is a signicant improvement over normal multiplication which is O(n^2). =========================================================================== Q6.2: What is an FFT? A: An FFT is a Fast Fourier Transform. These are often used in signal processing, and they are basically transforming a signal into a series of discrete sine and cosine waves. For more information on FTT's, see the following websites: "http://theory.lcs.mit.edu/~fftw/fft-links.html" FFT Introduction (many FFT links) "http://www.spd.eee.strath.ac.uk/~interact/FFT/" Fourier Transform in Signal Processing "http://cfatab.harvard.edu/nr/bookcpdf.html" Numerical Recipes in C (See parts on FFT) I have also heard that the book _Who is Fourier_ is quite good, though I have not read it. Thank you Vincent J. Mooney Jr. ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ Date: Fri, 16 Jul 1999 10:05:25 -0700 From: "John R Pierce" <[EMAIL PROTECTED]> Subject: Re: Mersenne: phew > > Well, the current range of Mp candidate values (just under 8,000,000) is > > described as using a 63 bit 'factor'... I would assume eventually this has > > to go to 64 bits, but I'm not clear on the relationship between the exponent > > and the FFT size and the 'fact bits' listed on the test status pages. > > OK, so you mean the exponent at which changeover from 63 bit trial > factoring to 64 bit trial factoring occurs. This is a bit over 9 > million. The "break" actually occurs where we want to do more than 64 > bits trial factoring... George's current code is just as good at > trial factoring to 64 bits as it is to 63 bits. and the FFT sizes? If I recall, right now we are doing ... ah, I found the table on George's site, duh. at 7,820,000 we just crossed over into 448K FFTs. at 9,090,000 we hit 512K at 10,380,000 we hit 640k. etc til > 20,500,000 exceeds 1024k so how big of a FFT can the current 18.x.x Prime95 handle? Up to 1024K FFTs? If so, I guess we still have some headroom... - -jrp ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm ------------------------------ End of Mersenne Digest V1 #598 ******************************
