Mersenne Digest Thursday, 21 May 1998 Volume 01 : Number 365 ---------------------------------------------------------------------- From: "Tim Charron" Date: Tue, 19 May 1998 09:30:30 -0400 Subject: Re: Mersenne: Use Fermat First? George Woltman wrote: > > I'll answer as a GIMPS programmer - not as a mathy people. > > The Fermat test would be a fine way to screen exponents before > a Lucas-Lehmer test is run *IF* it can be made to run significantly > faster than an LL test. At present, the two tests take the same > amount of time - so I use the definitive test rather than the > very-very-often correct Fermat test. > > The Fermat test requires p squarings modulo 2^p-1. > The LL test requires p squarings modulo 2^p-1 and p subtractions of 2. > > The subtractions of 2 cost nothing. So, the two algorithms have the same > cost. Given that we are testing exponents near 5,000,000 now, even if you > save a squaring, that's only a 1/5,000,000th improvement -- just > not worth the bother. What do you consider a significant improvement? Say that a way was found to make the Fermat test 1% faster than the LL test. This 1% faster would let every machine participating in GIMPS work 1% faster. Unless positive results (either actual primes found or false positives -- both requiring a recalc using LL) occurred more than 1% of the time, this would be a net gain for the entire effort. - -- Tim Tim Charron tcharron@ctfinance.com tcharron@interlog.com ------------------------------ From: "Guillermo Ballester Valor" Date: Tue, 19 May 1998 17:00:03 +0200 Subject: Mersenne: Fermat test to double-cheking ? Hi: Dr. P.Lawrence-Montgomery wrote: > One way to get consistent answers is to run it on bases > a = 27 = 3^3 and a = 243 = 3^5. To test Mp, one Fermat tester > repeatedly > squares 27 until he gets 27^(Mp + 1). If his final result is 27^2 = > 729, > then Mp is a likely Mersenne prime, and an LL test can follow. > Another tester computes 243^(Mp + 1). Even if both testers use the same > program, they are putting different data through the FFT code. > When done, the two testers report the bottom bits of > > [27^(Mp + 1)]^5 and [243^(Mp + 1)]^3 > > to a central site. The outcomes should agree, since both > are computing (3^15)^(Mp + 1). > > [Actually one should use (Mp + 1)/2 rather than Mp as the exponent, > checking whether the outcome is -27 or -243.] Does it means we can perform a double check using the SAME program with different starting points?. The mathematical comunity would accept two coincident residues in that form to demonstrate this exponent is NOT PRIME. If the answer is YES, note that a program with Fermat test to Mersenne numbers would have 99.99% of code coincident with LL-test and could run 0.01% faster ;-). I think that the probable primes this test would give are very, very few (we would need two or three LL test to confirm to or three new mersenne primes!). We have thousands of exponents to double-check, and most of people in GIMPS cannot made a double-check test because we need other program running in other machine. If we can use the Montgomery scheme to discard exponents it would be great!. Yours sincerely. PD. Doing Fermat test we can see if there is any mersenne number (exponent prime) base 3 pseudoprime. ************************************** Guillermo Ballester Valor c/ Córdoba, 19 18151-Ogijares (SPAIN) Phone: 34 58 597503 E-mail: gbv@ctv.es ************************************* ------------------------------ From: Will Edgington Date: Tue, 19 May 1998 10:50:12 -0700 Subject: Re: Mersenne: Use Fermat First? Tim Charron writes: George Woltman wrote: > The Fermat test requires p squarings modulo 2^p-1. > The LL test requires p squarings modulo 2^p-1 and p subtractions of 2. > The subtractions of 2 cost nothing. So, the two algorithms have the same > cost. Given that we are testing exponents near 5,000,000 now, even if you > save a squaring, that's only a 1/5,000,000th improvement -- just > not worth the bother. What do you consider a significant improvement? Say that a way was found to make the Fermat test 1% faster than the LL test. This 1% faster would let every machine participating in GIMPS work 1% faster. Unless positive results (either actual primes found or false positives -- both requiring a recalc using LL) occurred more than 1% of the time, this would be a net gain for the entire effort. Yes, this is true, _if_ the Fermat test is "enough" faster. But we don't know how much faster is "enough" because we don't know how often the Fermat test fails to identify a composite Mersenne. And remember that George is the person that knows the fastest LL program the best; after all, he wrote it. So I would think he'd know if a faster Fermat program could be written from it. On the other hand, between the source code for prime95 and the source code for Factor98, which also uses George's FFT code, I imagine someone out there with Intel assembler experience could pretty quickly write a Fermat test program that uses George's FFT code. Then we could directly compare the speeds and go from there. Any takers? Will ------------------------------ From: "Robin Y. Millette" Date: Tue, 19 May 1998 14:07:02 -0400 Subject: Mersenne: Weird thing - I think... Hello, I'm using the Prime95 client, 16.2.1, and something peculiar happened while factoring. Too bad I can't cut and paste from the client (that would make it friendlier), so here is what happened in a few words: While factoring a number, pass 16 of 16, the client hit a factor and reported it to the server, but then it went on a little more on that same number, continuing to factor it. Here are a few relevant numbers: Factored M5450153 thru 713149298*2^32 (pass 16 of 16)... Contacting server... Sending results for M5... M5... has a factor: 3345203594706648953 Done with server Factored M5450153 thru 733108354*2^32 (pass 16 of 16)... [and 2 more from same pass] If it found a factor, why would it continue with the same M? I understand that the LL test must go thru all passes before making any claim, but for factoring... I don't understand. Thanks for you time, begin 600 WINMAIL.DAT M>)\^(@,2`0:0" `$```````!``$``0>0!@`(````Y 0```````#H``$(@ <` M& ```$E032Y-:6-R;W-O9G0@36%I;"Y.;W1E`#$(`0V ! `"`````@`"``$$ MD 8`D $```$````0`````P``, (````+``\.``````(!_P\!````00`````` M``"!*Q^DOJ,0&9UN`-T!#U0"`````&UE``,P M`0```!(```!M97)S96YN94!B87-E+F-O;0````,`%0P!`````P#^#P8````> M``$P`0```!0````G;65R`/9?`0`` M`!(```!M97)S96YN94!B87-E+F-O;0````(!]U\!````00````````"!*Q^D MOJ,0&9UN`-T!#U0"`````&UE<1G'"X 80!J@ M!]$>H&D+(',Z%3I7&FPB`6Y^=0;0!) 7L!SA!" 7T"#\;V87P1>P'9D8X!R! M&J7[&$,)<' )$2&R!4 :X!:#Z0^PP_1I0>1Z5'U$M!3O%*-,L0OQ-/Q65%B 88#!1`9 8 M87,>4Q:23$P6@ >0!4!M^Q8P!4!G*+(RD0= `R E,K\'D23@-]$K01\0)%-N M12#[%U +<&TI=#?2&K@X\1O@OF0"(!PQ1^@TQ14T5 ^ ]&YK-[1Y"& 6@ =Q M%2;7$X !0!/",S\`-!4T$'$"`%,``````P`0$ `````#`!$0``````,`@!#_ M____0 `',.!2;*M/@[T!0 `(,.!2;*M/@[T!"P`!@ @@!@``````P `````` M`$8``````X4````````#``. "" &``````# ````````1@`````0A0`````` M``,`!H (( 8``````, ```````!&`````%*%``"W#0``'@`F@ @@!@`````` MP ```````$8`````5(4```$````$````."XP``,`)X (( 8``````, ````` M``!&``````&%````````"P`P@ @@!@``````P ```````$8`````#H4````` M```#`#& "" &``````# ````````1@`````1A0````````,`,X (( 8````` M`, ```````!&`````!B%````````'@!"@ @@!@``````P ```````$8````` M-H4```$````!`````````!X`0X (( 8``````, ```````!&`````#>%```! M`````0`````````>`$2 "" &``````# ````````1@`````XA0```0````$` @````````'@`]``$````!``````````,`#33]-P``E$P` ` end ------------------------------ From: Colin Percival Date: Tue, 19 May 1998 12:46:14 -0700 Subject: Re: Mersenne: Use Fermat First? >I'm still not clear where the mod M reduction is done. In frequency space or >in integer space? Well, as a very 'mathy' person, I'm probably going to get most of the details wrong, but I'll rely upon George to correct them. As I understand it, the mod M reduction isn't really 'done' anywhere, but rather we get it for free as a result of the FFT process. What an FFT multiply really does is multiply two polynomials modulo x^(2^n)-1 (or x^(k*2^n)-1 for small k). It does this by evaluating the two polynomials at the (2^n)th roots of unity, multiplying the values, and then interpolating the resulting polynomial. The advantage of the FFT is that it allows you to do the evaluating and interpolating in O(n*ln(n)) time instead of O(n^2) time. Note that I've been writing about multiplying polynomials. TO multiply two integers in the 'normal' FFT way, we write the integers in some convinient base (2^16, for example) and then pretend that it is really a polynomial. So, for a simple example, with base=2, tthe number 5 would be written as x^2+1. We then use the FFT multiply to multiply the two polynomials together, and then 'evaluate' the polynomials, which really just means handling carries from one position into the next. This is why we can't just stay in 'frequency space' (== the values of the polynomials). So to multiply 5 by 5, we would multiply x^2+1 by itself, getting the answer x^4+2*x^2+1. which we would turn into x^4+x^3+1 (== 25). Now in the form which GIMPS uses, the base isn't an integer. The base is set to 2^(p/(k*2^n)), so that the reduction mod x^(k*2^n)-1 which I mentioned above just turns out to be reduction mod 2^p-1. Normally, people have to zero-pad their polynomials, because they don't want to have a modular reduction. Here, we take it and use it to accomplish something we would have had to do anyway. Colin Percival ------------------------------ From: Chris Nash Date: Tue, 19 May 1998 20:39:35 -0400 Subject: Re: Mersenne: Use Fermat First? Colin > What an FFT multiply really does is multiply two polynomials modulo >x^(2^n)-1 (or x^(k*2^n)-1 for small k). It does this by evaluating the two >polynomials at the (2^n)th roots of unity, multiplying the values, and then >interpolating the resulting polynomial. I can't thank you enough for that wonderful explanation... suddenly everything makes perfect sense to me! Many thanks, that was incredibly helpful! Best Wishes Chris Nash ------------------------------ From: Peter-Lawrence.Montgomery@cwi.nl Date: Wed, 20 May 1998 06:55:30 +0200 (MET DST) Subject: Mersenne: Triple multiply (was: Use Fermat First?) One potential way to make Fermat faster than LL is to invent a fast FFT algorithm for multiplying _three_ numbers mod Mp rather than two. Cubing, in particular, would take the forward transform of the number being cubed, cube the outputs pointwise, and do a reverse transform, followed by the usual carry propagation and reduction mod Mp. With such as scheme, if we want to evaluate b^E (mod Mp) where E = 2^p is a positive exponent, we can write E in base 162, say E = (e_{k-1} e_{k-2} ... e_1 e_0)_162 To compute b^E, we might precompute b^j mod Mp for 0 <= j <= 161 (actually the forward transforms of these b^j). The left-to-right base-162 exponentiation algorithm initializes answer to b^(e^{k-1}) (table look-up) and repeatedly does 162 (next digit in exponent) answer <- answer b (mod Mp) This step needs four cubings, to get answer^81 from answer, and a three-way multiply to get the new answer. The major cost of the step is five forward-reverse transform pairs. Overall cost of the exponentiation is about 5p 5 log_162 (2^p) = ------------ ~= 0.68 p log_2 162 pairs of transforms, compared to p such pairs for the Fermat test. This may seem like a 32% improvement, but recall it requires designing an FFT capable of multiplying three numbers mod Mp. When we multiply two numbers mod Mp, using a length lng FFT, we write our residue in a base approximately 2^(p/lng) (actually the DWT has a mixed-radix system, but I'll ignore that complication). The bound on the coefficients of the polynomial product is about lng * 2^(2p/lng), since each coefficient of the polynomial product (mod X^lng - 1) is a dot product with lng pairs of coefficients bounded by 2^(p/lng). If our FFT outputs have pr bits of accuracy (where pr might be 40 using 53-bit IEEE arithmetic), we require pr 2p/lng 2 >= lng * 2 When multiplying three operands at a time, we instead require pr 3p/lng 2 >= lng^2 * 2 since each dot product is replaced by a sum with lng^2 products of three coefficients. For the small values of pr, such as pr = 40 bits, we already consume almost half of the accuracy bits just in the factor lng (about 262144 or 524288), and the lng^2 factor in the second inequality would doom us. On the other hand, if we design an FFT with a huge pr, such as 1024 bits, there is a faint hope. If p ~= 4 million, then a multiplier for two operands can use lng = 8192 and radix around 2^500. A multiplier for three operands can use lng = 12288 and radix around 2^330. An FFT for length 12288 will take 50%-60% longer than one for length 8192. If this FFT takes 55% longer, then (1.55) * (0.68) = 1.054, so we estimate a Fermat test will take 5% longer than an LL test. Perhaps somebody can improve this design so Fermat beats LL. Using base 486 rather than 162 gives a 1% improvement, for example. ------------------------------ From: "Chuck W. " Date: Wed, 20 May 1998 10:08:29 -0700 (PDT) Subject: [none] Although I realize that it is nothing terribly new, I have come across some things that interested me and I figured others might be interested: As we all should know, all primes MUST end in 1,3,7 or 9. Further, I have determined that all composites, made up of two primes, must end in 1,3,7, or 9 as well. Further this breaks down as follows: Let N be a composite number > 0 whose last digit is n, made up of primes P1 > 0 and P2 > 0 whose ending digits are p1 and p2 respectively. If n = 1 then (p1 = 1 and p2 = 1) or (p1 = 7 and p2 = 3) or (p1 = 9 and p2 = 9) If n = 3 then (p1 = 1 and p2 = 3) or (p1 = 7 and p2 = 9) If n = 7 then (p1 = 1 and p2 = 7) or (p1 = 3 and p2 = 9) If n = 9 then (p1 = 1 and p2 = 9) or (p1 = 3 and p2 = 3) Please note that only specific combinations are possible (hence the and/or). I can provide the proof if you need it. I won't waste the space at this time. What relevance does this have? It limits the possibilities for what the prime components could be by about 80% (or 60% if the composite ends in 1). It also shows that composites that end in 1, are stronger, with respect to trial division attacks, than composites that end in 3,7 or 9. I am not sure if this strength issue holds true for other factoring methods. Is this a case for revisiting trial division? IMHO absolutely not... I do believe this could be used with other optimizations to make factoring large composites a bit easier... Is there anyone who can take the time to explain the ppmpq method of factorization to me? The web seems to be sorely absent of any good explanations. Thank you... - - I tell you the truth, we speak of what we know, and we testify to what we have seen, but still you people do not accept our testimony. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : WWW+PGP: http://www.silverlink.net/poke : : E-Mail: chuckw@silverlink.net : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : According to Section 227(b)((3)(B) of US Code Title 47 I am entitled : : to $500 per un-solicited commercial e-mail. : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ------------------------------ From: "Ernst W. Mayer" Date: Wed, 20 May 1998 13:25:49 -0400 Subject: Mersenne: Re: Fermat base-3 for LL? Dear All: time to clear up this Fermat-base-3 business once and for all (i.e. until the next wave of newbies start nattering about it without bothering to look through this list's archives first.) Jean-Luc Cooke writes: >I've just tried the Fermat test with the new little bit of math Peter >showed me. > >a^( [N+1]/2 ) mod N = -a, for any "a" and N is prime. > >and have 50% savings in time compared to the LL test! I used the very >sophistacated "steamboat" counting system [ :) ] and the M(2203) LL test >took about 10 steamboats in Java while the Fast Fermat test took only 5! > >This is great stuff. I am now convinced we should 3-PRP test all >numbers before we go on to the LL tests. 50% savings at miniscule runlengths is MEANINGLESS - it's the large-p asymptotic behavior that really matters, and the asymptotic work for doing a Fermat test is the SAME as an LL test - one iteration more or less is completely negligible. I also wrote a base-3 program, over a year ago, and tested all p up to 60000 with it. Also no false positives, but as there's no proof such M(p)'s don't exist (and significant evidence that they might), I don't recommend using the code for primality testing. It's at ftp://nigel.mae.cwru.edu/pub/mayer/mersenne_cofactor.f90.gz Now, you may be asking why I bothered to write such a program if the test is no faster than LL and moreover not definitive (at least regarding primality - it WILL tell you for sure if the number is composite.) The answer lies in the above program name. The base-3 test will not prove primality of an M(p), but it can be used to quickly test the status of any cofactor of an M(p) with one or more known factors. This is because the Fermat-base-3 residue of an M(p) can be used (as with the Pe'pin test, which is really just a Fermat-base-3 test of a Fermat number) to perform a so-called Suyama posttest of the cofactor of the number in question. The Suyama test is described in many references on NT, (e.g. Riesel's book) so I'll not repeat the full description here. That is, the ONLY advantage of the Fermat-base-3 test is that it yields a residue which, if the number proves composite, is still of further use, unlike the LL residue, which is useful only for results verification. I gave a talk on extending the Suyama test to Mersenne numbers at last December's West Coast NT Conference, and also presented the probable-prime cofactors I identified using the above program. All of the cofactors under 3000 digits have since been proven prime (using either Morain's ECPP or Mihailescu's Cyclotomy program), but the 5 largest remain unproven: Cofactor Digits - --------------------------- ------ M14561/ 8074991336582835391 4365 M17029/ 418879343 5118 M28759/ 226160777 8649 M28771/ 104726441 8653 M32531/ 65063 / 25225122959 9778. George Woltman writes >The Fermat test requires p squarings modulo 2^p-1. >The LL test requires p squarings modulo 2^p-1 and p subtractions of 2. > >The subtractions of 2 cost nothing. You're absolutely right, George, but the "frequency-space-only" crowd is a stubborn bunch. Read on... Simon Burge writes: >If we don't need to subtract 2 each iteration, can we remain in >frequency space all of the time, and thus save the FFT/IFFT each >iteration? This would be a _HUGE_ saving. This has been discussed ad nauseum in this group. I do wish people (not you in particular, Simon - this is a general complaint :) would read the archives before starting yet another "new" thread which is not new at all. The frequency-space-only conjecture is specious, because it ignores fact that the rounding/propagate-carries/subtract-2 step in a floating point application is absolutely necessary to get rid of FP convolution errors prior to the next iteration. Thus, we do an IFFT not just to ease the subtract-2 operation - if that were all, we could easily do it in frequency space, owing to the linearity of the FFT and the fact that the FFT of a vector with only one nonzero leading element just gives a vector with that initial element in every slot. Rather, we have to do the IFFT to get back to a space where we can identify (with overwhelming, but not absolute) certainty what part of each vector element is the true residue and what part is accumulated round-off error. Yes, it's possible to do 2 or more iterations before IFFT'ing, but then one has to choose a digit size so small that one's vector length shoots right through the roof, more than offsetting the gain obtained by doing fewer (I)FFTs. Put plainly, it's a blind alley, albeit one with a very tempting-looking entrance - you might say it's the algorithmic equivalent of a seedy dive fronted by a "Girls! Girls! Girls!" sign. (I apologize to our female readers for the clearly chauvinistic analogy. Perhaps the sign should say "Live! On Stage! Totally Naked!" without specifying gender, species or even kingdom - for all you know, there might be a petri dish covered with archaebacteria on that stage :) 'Nuff said, - -Ernst ------------------------------ From: Jean-Luc Cooke Date: Wed, 20 May 1998 16:54:00 -0400 Subject: Mersenne: Re: Chuck W. wrote: > > Although I realize that it is nothing terribly new, I have come across > some things that interested me and I figured others might be interested: > > As we all should know, all primes MUST end in 1,3,7 or 9. Further, I have > determined that all composites, made up of two primes, must end in 1,3,7, > or 9 as well. Further this breaks down as follows: Anything that ends in an even digit {0,2,4,6,8} is even therefor not prime. Anything that end in {0,5} is divisible by 5 therefor not even. Any odd number multiplied by and odd number gives and odd number, a number ending in {1,3,5,7,9}. Seeing how any prime number can't end in {5}, you can't have "....1" x ".....5" = ".........5", can't happen. It's easy to see that. My grade 6 teacher taught us that when we started to learn how to multiply. Ahh that was when I first started to learn how to cheat on math tests. :) > Let N be a composite number > 0 whose last digit is n, made up of primes > P1 > 0 and P2 > 0 whose ending digits are p1 and p2 respectively. > > If n = 1 then (p1 = 1 and p2 = 1) > or (p1 = 7 and p2 = 3) > or (p1 = 9 and p2 = 9) > If n = 3 then (p1 = 1 and p2 = 3) > or (p1 = 7 and p2 = 9) > If n = 7 then (p1 = 1 and p2 = 7) > or (p1 = 3 and p2 = 9) > If n = 9 then (p1 = 1 and p2 = 9) > or (p1 = 3 and p2 = 3) > > Please note that only specific combinations are possible (hence the > and/or). I can provide the proof if you need it. I won't waste the space > at this time. > > What relevance does this have? It limits the possibilities for what the > prime components could be by about 80% (or 60% if the composite ends in > 1). It also shows that composites that end in 1, are stronger, with > respect > to trial division attacks, than composites that end in 3,7 or 9. I am not > sure if this strength issue holds true for other factoring methods. True, but you'll find that this is what's used in the FIRST steps of attempting anything in primality. > Is this a case for revisiting trial division? IMHO absolutely not... I do > believe this could be used with other optimizations to make factoring > large composites a bit easier... it would if we were using a method that actually looked at the things you just mentioned. But methods like Fermat and LL use these properties at the Proof level and they can ignore then in the application level. At least you can think of it that way. > Is there anyone who can take the time to explain the ppmpq method of > factorization to me? The web seems to be sorely absent of any good > explanations. Humm, ppmpq? Haven't heard of it. I'm sorry if I seem to have come down hard on you here, I didn't mean it as such. I've been down this very path myself when I really started to take an interest in Num.Th. Keep doing this though, this is exactly how I taught myself the basics of modular arithmetic. Wanna see how sure I was that I was going to develop something new? http://www.engsoc.carleton.ca/~jlcooke/RSA/ It turned out to be Gauss' difference of squares factorization. Boy did I feel dumb! TTYL JLC - -- < censored :) > ------------------------------ From: "Gilles Polus" Date: Thu, 21 May 1998 09:23:35 +0200 Subject: Mersenne: FFT ??? I don't stop to see the word FFT. But, what means this word ? I want also to know what are the Carmichael's numbers. ------------------------------ From: Harald Alvestrand Date: Thu, 21 May 1998 09:51:53 +0200 Subject: Re: Mersenne: Re: Fermat base-3 for LL? At 13:25 20.05.98 -0400, Ernst W. Mayer wrote: > >Dear All: time to clear up this Fermat-base-3 business once and >for all (i.e. until the next wave of newbies start nattering about >it without bothering to look through this list's archives first.) No offense, but.... can we read this as a request for relatively frequent posting of a FAQ (or FAQ URL)? I know something of how hard it is to find facts in old mail archives.... Harald - -- Harald Tveit Alvestrand, Maxware, Norway Harald.Alvestrand@maxware.no ------------------------------ End of Mersenne Digest V1 #365 ******************************