Mersenne Digest Wednesday, July 28 1999 Volume 01 : Number 605 ---------------------------------------------------------------------- Date: Mon, 26 Jul 1999 19:56:34 -0700 From: "Joth Tupper" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Stepping out on a limb here I hope that this does not read like a flaming response. I have never seen anything that I could call "easy" in any aspect of modular forms, functions, automorphic functions, elliptic (and other algebraic) curves, or any of the other supporting struts in the background for Taniyama-Shimura or Wiles' work. What little I know I find generally confusing and very tough. Maybe if I pound the rocks 18 hours a day for 6 years I could get closer to a real understanding, but I have to settle for real time efforts (3 hours a day for the next 36 years...) The toughest math course I ever took was a graduate seminar of Shimura's (long ago) on automorphic forms. There may well be an easy way to do this stuff but I do not think anybody knows what it is yet. By all means look! Sometimes the computer application is simpler than the number theory. The easiest related derivation I know is showing how even values of the Riemann zeta function are related to coefficients of the cotangent series. Nobody even has a "nice" formula for the Bernoulli constants yet. (And they have been on the table for centuries.) (IMO, the LL test is nice compared to finding Bernoulli numbers.) The simplest pair of modular forms parametrizing an elliptic curve are the Weierstrass P function and its derivative. These are not easy functions to mess with but they are certainly the best known. Joth - ----- Original Message ----- From: Geoffrey Faivre-Malloy <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Sunday, July 25, 1999 9:40 AM Subject: Mersenne: Stepping out on a limb here > I'm rather new to much of the theory behind all of this so have mercy :) > > I just finished reading Fermat's Last Theorem which is a fascinating book. > This introduced me to the Taniyama-Shimura conjecture and subsequent > theorem. I've noticed that there are algorithms based on Elliptic Curves. > The Taniyama Shimura theorem says that you can directly map each Elliptic > curve to it's Modular form. > > Recently, a new theorem was proved that lets you solve Elliptic equations > easily with the Modular form - see > http://www.academicpress.com/inscight/07091999/grapha.htm for details. > > So, based on all of this, would there be some way write a program that used > these details to factor faster? > > G-Man > > _________________________________________________________________ > Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm > Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers > _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 27 Jul 1999 00:29:03 EDT From: [EMAIL PROTECTED] Subject: Mersenne: Down With The Evil Thread Hello, again. As before, I'm replying to a bunch of different people. And I have trouble thinking up decent subject lines as well. :-] <<So, based on all of this, would there be some way write a program that used these details to factor faster?>> I don't think that elliptic curves are useful in the small trial factoring that GIMPS does to weed out candidates, but I might be wrong. <<OK. Then what about John Sweeney? Jason Kline? Crandall & Fagin? How about the people that wrote factoring code?>> Lucas's and Lehmer's heirs! <<As others have noted, this is a big can of worms that's just complicating things without really adding anything to the effort itself.>> Right on. <<It's actually worse than this. I never intended to copyright any of the code I distribute, in part because some of it is already covered by copyright and/or patent for commercial purposes. Is trying to claim the EFF prize a commercial purpose? Don't ask me; I'm not a lawyer.>> And it gets muckier. :-< <<Just a quick note to praise the 'common-sense' posters on this list - I hope we all know who they are - it's much appreciated when one of them puts a stop to a thread which was getting way out of hand. Many thanks to STL for this one... in particular>> Thanks. :-) **** >It's amazing what money will do to people. In >a way, I almost wish that EFF had never come up with their prizes I'll paraphrase another quote on this as well, "A *person* is intelligent. *People* are irrational and dangerous". As individual human beings, we're quite good at distinguishing what is important to us personally. The whole EFF thing was supposedly to inspire advances in distributed computing - but instead has encouraged mass mania and reduced the thing to a lottery. I'd much rather the world factor the meager 200+ digits of 2^727-1, than find a 10M+ digit prime and fight over money. Isn't mathematics, science, human knowledge in general above things such base and vile as money? Are we all guilty of knowing the price of everything, but the value of nothing? Is bigger necessarily better? **** Mass mania is a very appropriate term. Or, rather, what _could_ happen if the GIMPS project goes and sets up the very things I mentioned would be bad in my last post/mail. <<Otherwise, let's get some rationality in here. We search on - and let's not let our areas of research and individual interests be controlled by potential financial gain. Let's follow through with STL's common-sense conclusions. AND ABOVE ALL, LET'S KILL THIS THREAD.>> [Emphasis STL's] Right on. Truer words were never spoken. <<Well, the likelyhood that a failure occurs may be 1%, but the likelyhood that a double check will not catch it is much lower. This is do to the fact that (barring bugs), the likelyhood that the numbers produce the same 64-bit residue is very, very low. Probably somewhere between 2^-64 and 2^-128.>> Ah, a product of my own brain drain. You're right, I stand corrected. So, does the rate of needed triple-checks conform with what a 1% error rate per test would indicate? (i.e. 1% * 1%, I think.) <<Suppose the number you're testing is N. If we assume N is prime, then quadratic reciprocity could be used to determine whether your base a is a QNR. So pick your base a, do your test, which proves QNR and hence primality (Proth's theorem basically states the Euler criterion for a QNR is necessary *and* sufficient to prove primality). If you don't get what you expect from the quadratic residue symbol, then it's composite. (Look up 'Kronecker symbol' - basically, an excuse to use quadratic reciprocity whether or not you know N is prime).>> We need more talk like this (and maybe some that I understand better. :-D ) on the list and less of the evil thread. <<what if they set some clear contractual conditions? Mumbo jumbo isn't strictly needed. >> My opinion is that anything legal/contractual is EVIL Jabibbian nonsense and must be avoided at all costs. <<No they won't, because the start-up marketing would be too difficult. As long as the GIMPS contractual terms are reasonable, there will be no motivation to compete.>> "Marketing"? I wish that I never heard that word so much as spoken (typed?) on this list. **** > That would not be a good thing. It's amazing what money will do to people. In > a way, I almost wish that EFF had never come up with their prizes, so we > could have avoided all of this unpleasantness. what's unpleasant about speculative free speech? **** The prize's effects are unpleasant. Not the rest of what EFF does. <<points one and six seem contradictory.>> We can't STOP the EFF from awarding money. But we can't and SHOULDN'T change any way in which it's being done now, which includes dividing up money in some Jabibbian manner. In my opinion, as long as _nothing_ changes with what's being done now, GIMPS isn't really in danger. Jump-aheaders will not be that much of a problem because testing that large will take a LONG time with present computers - I think. <<1) What is the approximate P-90 computing time to test for primality for a 1, 10, 100 million (& 1 trillion!) digit Mersenne Primes?>> Generally, a billion comes after 100 million, but I can't remember how the British and other countries work with billions. And I don't think that many people run P90s now for GIMPS.... I hope. <<3) Assuming the continued (exponential?) growth of GIMPS, when will GIMPS begin to assign work in each of these areas?>> GIMPS's growth, sadly, doesn't _seem_ to be exponential, and the chart on entropia.com STILL looks linear to me, though a parabolic curve is now fitted to the data on the page. (A cubic curve would fit it even better, and a quartic yet better! Fourier strikes again! Run for your lives!) <<Of course I understand that there is a higher purpose to GIMPS than the money - and that it would be better to "fill in the tables" of N than just skip to the area that would yield prize money.>> Yes. <<I further suspect (perhaps someone agrees?) that GIMPS will run out of steam when it starts reaching the values of N that might yield 10 million digit Mersenne primes... This is because the average home PC will no longer be able to complete a primality test in a reasonable amount of time.>> Remember, computers seem to always be getting faster, and every once in a while we get an algorithm improvement (much more sporadically than the seemingly-dependable computer speed increases). Witness the steady progression of 8086 - 80186 - 80286 - 80386 - 80486 - Pentium - Pentium Pro - Pentium II - Pentium III.... When a large portion of GIMPSters are running Intel McKinley 1.2GHz computers with 4GB of SLDRAM, testing a decamegadigit Mersenne number will be a LOT quicker than on a pokey Pentium III 550Mhz. <<Or perhaps people feel that home computers will catch up in power with the added work of larger N's and won't be a problem in future years?>> Moore's Law. Computers double in power approximately every 18 months. Has worked for over a decade. Will _probably_ work for at least the next 5 years and even up until 2020. At or around 2020, transistors hit the .01 micron quantum limit, and "conventional" computing reaches its peak. Then, we break out the Pentium XIV Quantum Computers, and proceed merrily on our way. :-) Well, that's it. I don't think I need a summary this time. I think. S.T.L. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 27 Jul 1999 07:40:56 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Down With The Evil Thread ><<1) What is the approximate P-90 computing time to test for primality >for a 1, 10, 100 million (& 1 trillion!) digit Mersenne Primes?>> >Generally, a billion comes after 100 million, but I can't remember how the >British and other countries work with billions. And I don't think that many >people run P90s now for GIMPS.... I hope. Why not? A P90 adds 1 P90 CPU year per year (give or take). Not everyone can afford a PIII/550. ><<Or perhaps people feel that home computers will catch up in power with >the added work of larger N's and won't be a problem in future years?>> >Moore's Law. Computers double in power approximately every 18 months. Has >worked for over a decade. Will _probably_ work for at least the next 5 years >and even up until 2020. At or around 2020, transistors hit the .01 micron >quantum limit, and "conventional" computing reaches its peak. Then, we break >out the Pentium XIV Quantum Computers, and proceed merrily on our way. :-) By that time (hopefully) the Intel architecture will be dead. I *really* hope that mass market computers in 2020 are not backwards compatable to the 8086, as that would be truly stupid (after all, my computer isn't backwards compatable to Multivac). In fact my computer would probably be much better off if it weren't backwards compatable to the 8086. Imagine how fast a version of George's program would be if everyone used ULTRASparc or MIPS or whatnot instead of the Intel... - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 27 Jul 1999 09:27:50 -0400 From: "Geoffrey Faivre-Malloy" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Stepping out on a limb here > I hope that this does not read like a flaming response. I have never seen > anything > that I could call "easy" in any aspect of modular forms, functions, > automorphic functions, > elliptic (and other algebraic) curves, or any of the other > supporting struts Nah, not a flame at all :) Isn't the English language lovely? Easy is *SO* relevant. That's not to say that it would be easy for me either :) I suppose that's the trouble when someone like me reads a document that was intended for laymen and ponders about the implications :) G-Man _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Tue, 27 Jul 1999 16:28:41 +0000 (GMT) From: Henrik Olsen <[EMAIL PROTECTED]> Subject: Re: Mersenne: Down With The Evil Thread On Tue, 27 Jul 1999, Lucas Wiman wrote: > ><<1) What is the approximate P-90 computing time to test for primality > >for a 1, 10, 100 million (& 1 trillion!) digit Mersenne Primes?>> > > >Generally, a billion comes after 100 million, but I can't remember how the > >British and other countries work with billions. And I don't think that many > >people run P90s now for GIMPS.... I hope. US: million 10^6, billion 10^9, trillion 10^12 ... Non-US: million 10^6, milliard 10^9, billion 10^12, billiard 10^15, trillion 10^18 ... In general, US <num>llion 10^(num*3+3) non-US <num>llion 10^(6*num), <num>lliard 10^(6*num+3) - -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ Animal behaviour is best described by the four F's Feed, Fight, Flee and Reproduce _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 28 Jul 1999 00:05:59 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Evil, evil prize thread On 26 Jul 99, at 17:12, David L. Nicol wrote: > Are you In It For The Money currently? No. Actually I stumbled across GIMPS by accident when I was looking for "free" floating-point benchmark programs, though I did have a long-standing latent interest in the topic. At that time the prize was $1100, I can honestly say that this made no difference one way or the other. I've never played our national lottery because I realize that it's a long-term loser (betting on the gee-gees is _much_ more effective as an "investment", but I don't do that, either). In fact, participating in the project has cost me several thousand dollars in terms of electricity bills and hardware upgrades that wouldn't have been neccessary otherwise, but, hey, I've had fun participating! > > I've got an idea -- let's set up a fake seti@home client that runs > a randomized seti@home graphical lookalike display but secretly connects > to > entropia for assignments -- Ha! Not such a good idea. That is, at best, deception, at worst, "misuse of electricity" (as the archaic law here has it). I want to encourage volunteers so _they_ can have fun, too - foisting something onto people without their consent deprives them of the joy of participation. > points one and six seem contradictory. I think we need LMJ to > properly cope with the appearance of the EFF awards, and keep GIMPS > a just-for-fun activity. What's wrong here is a (well-meaning but apparently misguided) attempt to "change the rules" within GIMPS. Also, advertising a prize (awarded by someone else) but then indicating that you might get only a fraction of that amount if you win is not really honest. I'm sensitive and sympathetic to what George & Scott are aiming at, but I'm coming round to the opinion that the best thing to do is to go back to the position on the $50K EFF prize - let it be awarded to the discoverer & trust that some filters back. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 28 Jul 1999 09:30:39 +0000 From: Yann Forget <[EMAIL PROTECTED]> Subject: Mersenne: Fermat number & others Hi, I have a few questions which are not in the FAQ : - - What about testing F24 with Pepin's test ? (http://www.utm.edu/research/primes/glossary/PepinsTest.html) Is there a code for this ? On Intel (MS Windows or Linux) ? Is there some machine running this ? How long would it take to test the primality of F24 with a PII (for ex.) ? Is there a mailing list about Fermat numbers? - - Long ago ;-) I made some investigations about the period of inverse of prime numbers (1/p) (Is this good English ?). I found an empiric relation between the number of digits of the period (d) et the fact that p is prime, namely that d is a divisor of p-1. I have been told that this was proved by Gauss. Is there a Web page about this ? Is this could be of any use in the search for large primes ? Thanks for your answer. Yann - -- Ionix Services, les services r�seaux d'aujourd'hui http://www.ionix-services.com/ Tel 04 76 70 64 24 Fax 04 76 70 64 25 _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 28 Jul 1999 10:43:39 +0100 From: Gordon Spence <[EMAIL PROTECTED]> Subject: Mersenne: Re: Mersenne Digest V1 #604 STL137 wrote: >A summary of my opinions, so others don't need to respond directly to my >(unfortunately) long message: >1) Prize money should go to one person (or small team): The discoverer. >2) A non-profit corporation to divide any prizes must NOT be created. 100% agree >3) Orderly checking of exponents is vital. sorry, it's up to me what i do, they all get done in the end >4) We must make all attempts to not entice others to create competing efforts >to check Mersenne primes, as it would lead to chaos. aahh, a new thread on chaos theory <G> >5) We need new archives for this list, as the current ones seem to be >dead/broken/seriously outdated. I have the digests from 383 onwards, I can put them up for download on my web-site if anyone is interested. >6) Legal mumbo jumbo must be avoided. I like GIMPS the way it was, before EFF >prizes, and nothing ought to be changed. 100% agree. What was that saying about money being the root of all evil ;-) and also wrote > ><<Are you In It For The Money currently?>> > >Absolutely not! I joined before this money kookiness, and do it for the fame. Yep, the fame. It's kinda nice to be in demand from radio, tv & press for a while. G _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 28 Jul 1999 08:04:47 -0400 From: Pierre Abbat <[EMAIL PROTECTED]> Subject: Re: Mersenne: Fermat number & others > - Long ago ;-) I made some investigations about the period of inverse of > prime numbers (1/p) (Is this good English ?). > I found an empiric relation between the number of digits of the period > (d) et the fact that p is prime, namely that d is a divisor of p-1. I > have been told that this was proved by Gauss. Is there a Web page about > this ? Is this could be of any use in the search for large primes ? The number of digits in the period is whatever power of 10 you need to make 1 mod p. If 10 is a primitive root of p, then the period is p-1. Ex. 1/7=.(142857), 1/17=.(0588235294117647). 16, of course, is not a primitive root of anything, so reciprocals never have full period in base 16, and most of them have odd period. phma _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 29 Jul 1999 00:39:44 +0100 From: Nick Craig-Wood <[EMAIL PROTECTED]> Subject: Re: Mersenne: Down With The Evil Thread On Tue, Jul 27, 1999 at 04:28:41PM +0000, Henrik Olsen wrote: > US: million 10^6, billion 10^9, trillion 10^12 ... > > Non-US: million 10^6, milliard 10^9, billion 10^12, > billiard 10^15, trillion 10^18 ... Actually I think most UK people would use the US definitions now-a-days (except maybe *really* old people ;-) I certainly would... - -- Nick Craig-Wood [EMAIL PROTECTED] http://www.axis.demon.co.uk/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Wed, 28 Jul 1999 23:24:39 -0500 From: Ken Kriesel <[EMAIL PROTECTED]> Subject: Re: Frequency of residue error (was Mersenne: Down With The Evil Thread) At 12:29 AM 1999/07/27 EDT, [EMAIL PROTECTED] wrote: >Hello, again. As before, I'm replying to a bunch of different people. And I >have trouble thinking up decent subject lines as well. :-] ... ><<Well, the likelyhood that a failure occurs may be 1%, but the likelyhood >that a double check will not catch it is much lower. This is do to the >fact that (barring bugs), the likelyhood that the numbers produce the same >64-bit residue is very, very low. Probably somewhere between 2^-64 and >2^-128.>> > >Ah, a product of my own brain drain. You're right, I stand corrected. So, >does the rate of needed triple-checks conform with what a 1% error rate per >test would indicate? (i.e. 1% * 1%, I think.) Something close to that, although the %-per-check is believed to be an increasing function with p. One would expect that of forty thousand LLtests and double checks, a few occurrences of both being wrong for the same p would occur, and that is what we've found; there were some months back, questions raised about a short list of exponents which had 3 tests done and no matches found, requiring (at least) a 4th test. George Woltman's estimates of about 1 in 100 were posted March 5, 1999, and made a distinction between V17 error rates and earlier versions. I wonder if the V17 statistics were affected by the shift count bug discovered later. Prior to this there was a thread October 13-15, 1998 about when triple-checking fails to produce matching residues. (Two residues wrong by random error would produce separate residues not matching a hopefully correct third residue, necessitating a _fourth_ test to hopefully obtain a match.) At that time, for exponents below 2,000,000, there were about 40,000 double checked exponents which appeared to fit a 1 in 100 independent error rate. A plausible distribution for that would be: about 99%, 39600 where first and second were both right about .99%, 396 where a third test produced a match about .01%, a few where triple-testing produced no match of those last few, likely all would be matched after a fourth LLtest. One might need a fifth or higher test, but at low odds (~4%) All those figures are sensitive to the actual error rate, of which 1% is only an approximation. ><<1) What is the approximate P-90 computing time to test for primality >for a 1, 10, 100 million (& 1 trillion!) digit Mersenne Primes?>> .589 seconds/iteration for a 1-million decimal digit mersenne prime, or about 23 days, assuming the use of prime95. For the other sizes of exponents, no released version of prime95 supports running such high exponents. Runtimes can be estimated as roughly p~=#digits/log10(2) t/t0= p^2 log(p) / (p0^2 log (p0) ) Then: digits P90yr p90sec/iter 10^6 .062 .589 10^7 7.23 6.87 Hardware failure before completing 1 test is a risk 10^8 826. 78.5 Someone will surely poach the exponent before completion 10^9 93000. 883.5 (The EFF's big money appears to be safe!) Ken [EMAIL PROTECTED] _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #605 ******************************
