Mersenne Digest Saturday, October 16 1999 Volume 01 : Number 645 ---------------------------------------------------------------------- Date: Fri, 15 Oct 1999 20:03:02 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Modular arthimatic.. On 15 Oct 99, at 18:25, Chris Jefferson wrote: > Just something I was pondering a couple of days ago... > > Consider a general number (odd) number c which can be factored into ab=c > > W.L.O.G. assume b is greater than a > > then let x=(a+b)/2 , y=(b-a)/2 > > then (x+y)(x-y)=c > > x^2 - y^2 = c > > x^2 = c + y^2 > > So if we can find if this equation has any integer solutions, we've found > our factors... > > Ways of doing this: > > The difference of two squares is always an arthimetic progression of odd > numbers. Here is an example.. > > 2^2 - 1^2 = 3 > 3^2 - 2^2 = 5 > 4^2 - 3^2 = 7 > > and so on... So look at general sum of an arthimetic series > > S(n) = (n/2)(2a + (n-1)d) In this case d=2 and a is odd, so need to try to > solve c = na + n(n-1)/2 for integers n,a > > Also, try to solve x^2 - y^2 = 0 mod c Are we not back to Fermat's Method for factorization (again)? If we're dead lucky and pick a value c such that a and b are very similar in magnitude, this method works a treat (hence it's very unwise to pick a public key which factorizes into two nearly equal numbers. You make the job of cracking your key a lot harder if you pick the product of two numbers which differ in length by a couple of bits.) There is still a gap between the largest factors which can be found (practically, not theoretically) by techniques suited to "small" factors, like trial factoring, P-1 and even ECM, and Fermat's Method which is practical only for "small" values of b-a. (Fermat is just plain _awful_ at factorizing 3*p for large prime p!) Probably the continued fractions method is the best line of attack on numbers which resist "reasonable" efforts with other methods. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 21:34:02 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: splitting up 10m digit primes On Thu, Oct 14, 1999 at 06:15:52PM +0100, Chris Jefferson wrote: >In my personal opinion, the best way of doing this would be to set up 3 >computers in a 'loop' all doing the same exponent. Then they could >communicate at regular intervals. We are already doing this manually, although only with 2 computers (if the residues match, you don't need the 3rd one). We're taking residues every one million iterations, and mail them to each other. So far, they've matched :-) And if one machine is faster than the other -- well, then it goes on to another exponent. No waiting needed. /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 17:10:58 EDT From: [EMAIL PROTECTED] Subject: Mersenne: The Mysterious Ways of S.T.L. Hello, everybody. As usual I'm quoting different people. Disturbingly, I noticed a weird HTML tag on my last E-mail. I can assure you I didn't put it there, and don't know why my software's acting up on me (because I've never seen that jibberish before). HTML mail is evil, only second to MIME. Long live ASCII! Please excuse my delay in sending this message. <<Also, if this extrapolation of the number of digits is accurate, there is another prime between the 37th & 38th(p=6972593) discovered primes. Unfortunately, the extrapolation of P just didn't go well. Actually, the extrapolated 39th mersenne prime is 6.34% off of 2^6972593-2. I suppose that's not so bad. That would also mean one was skipped. So it is currently my fairly strong opinion that a mersenne prime was skipped between the 37th & 38th discovered primes. I reserve the right to change my mind at any instant. I'd also guess that the skipped prime may have been pretty close to 2^5014947-1, and have a number of digits close to 1408773.>> This is similar to the conjecture I made oh-so-long ago. 6.9M was confirmed, but at the same time I had to predict a missing one (which I said was probably in the 4M range, but that's far less certain). <<[EMAIL PROTECTED]: I'm really looking forward to hearing how you made your estimates.>> << How did you make this estimate ? Fit an exponential curve to the known primes, and extrapolate the 1st one that should have at least 1m digits?>> <<Who knows the mysterious ways of STL?>> I usually just go by S.T.L. (my initials). <<At some point I had a vague recollection that STL had believed there was a number missing, and I was quite happy to see that it basically matched what I got. And rounded, my estimate for #39 equals his. >> Your estimates are close to what I have. I haven't the slightest idea how one establishes priority for a discovery, but here I go. I think I've improved on the conjecture of Wagstaff, Gillies, Lenstra, Pomerance, et al. (At the very least, it's another conjecture.) Some time before I E-mailed the list with my 3 conjectures I had made the main one. I had not told the list of it because I planned to use it in a ridiculously important paper for school. But it seems that my method is being rediscovered and I may as well announce what I've seen. Here it is, and what led me to it. I had picked up _Unsolved Problems in Number Theory, Second Edition_ by Richard K. Guy, and was reading it. In section A3 (which contains a humorous typo), I found the following: <<Suppose M(x) is the number of primes p <= x for which 2^p - 1 is prime.... Lenstra, Pomerance, and Wagstaff all believe this [an early conjecture by Gillies] and in fact suggest that ?? M(x) ~ e^gamma log x ?? where the log is to base 2.>> So I started investigating this. Armed with a copy of all Mersenne primes (I have a bad habit of saying this when I really mean exponents for which the Mersenne number is prime) from 2 to 3021377, a loyal TI-92+, and a newly gained knowledge of basic statistics, I started computing some things. First, I made a list of numbers 1-37. And I had the list of exponents, sorted by size. (I called it mersenne.) Then I plotted points with the 1-37 values for X and log[2] (Mersenne) for y. I got an astoundingly linear graph, as others have. Then, I plotted e^gamma log[2] (mersenne) versus the list of 1-37. Alongside this I graphed y=x. This is because the y=x line represents the Wagstaff conjecture. (If all exponents for which the corresponding Mersenne number is prime followed the Wagstaff conjecture exactly, e^gamma log[2] (mersenne) would equal 1, 2, 3, 4, 5, for each exponent in turn.) This was a rough measure of how well the Wagstaff conjecture applies to the actual set of Mersenne prime exponents. This graph seemed a little strange. So, I graphed e^gamma log [2] (mersenne) - (1, 2, 3, 4, etc). This represents how far off the Wagstaff conjecture is when applied to the data. (The Wagstaff conjecture *should* say that M(3021377) = 37, but it doesn't. This is why I graph this jibberish). This graph was INCREDIBLY disturbing. Save for one Mersenne prime, all these "errors" were above 0, and often big. Ech! So, I used my TI-92+ to take a linear regession line of this data (because I had recently learned how to do regression lines and correlation coefficients). This line was Y = .004769x + 1.4615. See what's happening here? It seems that there's a consistent error (1.4615) in the Wagstaff conjecture that doesn't change as the Mersenne primes grow (the .004769). So I went back and applied this correction to the graph "that seemed a little strange" and it fit y=x much better. Hence, my new conjecture: ?? M(x) ~ e^gamma log[2] (x) + C ?? Of course, I used 1.4615 to make my 3 conjectures to the Mersenne mailing list. In reality, I'm guessing it might be 1.5, or even 2^(1/e^gamma)! (In fact, I'd rather go with 2^(1/e^gamma), as Erhardt chose 1.5 for the e^gamma in the conjecture and now several mathematicians call the Erhardt Conjecture "probably false") This is mildly disturbing, of course. I think I haven't screwed up in formulating this conjecture (i.e. understood the conjecture stated in Guy's book correctly). I know it's based on only empirical evidence and no heuristic arguments. Please comment on it. When my ridiculously important paper for school is done, I'll post it and give the address to the Mersenne mailing list. (But I can't recieve help from you guys. :-S ). Thanks, S.T.L. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 17:14:30 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: types of work to request - 10m digit prime vs. next prime > Conjecture time: The prime number earning the $150K prize will not be a > Mersenne. This isn't so much a conjecture as a prediction (there is a difference). A conjecture is a very specialized prediction. > Why do I say that? Even with processor speeds increasing, we have a good > idea how long it'll take to find big primes by Lucas-Lehmer. Even for the > 10M-digit prime it'll be a damn long time the way we are doing it now. > Finding the monsters requires an intellectual leap by someone - possibly > in processor design, more likely in number theory. Admittedly this leap > may well be a better version of L-L in which case Mersennes will still be > the record primes for a long while to come. But my hunch is that there is > a better chance of finding some new way to either construct primes, or to > test some other special-form number, than there is of dramatically > improving on Lucas-Lehmer. Just a hunch. I might be wrong. I hope I live > long enough to see all of the EFF prizes awarded, whether to Mersennes or > not. Ok, it seems doubtful that we will ever be able to find a test more efficient than the LL test. The LL test involves p multiplications mod Mp, which is pretty impressive. However, I agree with your prediction because there are much more targeted types of numbers with similar running times (e.g. Proth numbers). As Chris Nash pointed out, a Proth test would have taken 1/4th the time of the LL test on the Mersenne found in June on a number of precisely 1,000,000 digits. You may be right about the construction of prime numbers. Also if someone were to find a faster way to multiply than an FFT convolution, that would dramatically improve primality testing. > PS - On an unrelated note --- what is the smallest natural number that is > not known whether it is prime or composite? Surely *someone* out there is > trying to work from the bottom up and factor every number. (I don't know > the answer. I am guessing the it is a smallish number of maybe 15 or > so decimal digits?) Probably the one right after the largest sieved interval. But I have to ask the question: Who cares? Unless the larger sieved limit is showcasing a new sieving algorithm, then why does it matter? To verify the primality of numbers up to a hundred digits is a simple matter. Just my $0.00 worth. (the FSF's motto) - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 17:45:06 -0400 (EDT) From: Darxus <[EMAIL PROTECTED]> Subject: Re: Mersenne: Islands of Truth I've put a graph of these "pairs" up on my web page. http://www.op.net/~darxus/p_pairs.bmp Numbering each P by the order in which they were discovered (and omitting #38), I put the even numbers on 1 line, and the odd numbers on a seperate line, and added 1 to the beginning of the evens to get them to line up. This does not look random to me. I am aware of and have some understanding of the argument that we humans are rather good at seeing paterns where there are none. I meerly wished to provide this graph for those who are curious and do not wish to take the time to plot it themselves. __________________________________________________________________ PGP fingerprint = 03 5B 9B A0 16 33 91 2F A5 77 BC EE 43 71 98 D4 [EMAIL PROTECTED] / http://www.op.net/~darxus Join the Great Internet Mersenne Prime Search http://www.mersenne.org/prime.htm _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 23:15:43 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: splitting up 10m digit primes On 14 Oct 99, at 18:15, Chris Jefferson wrote: > > Also one would have to ask what would be the incencitive for someone to act > > as a backup server... or prevent them from "stealing the work" as it were, by > > using high-speed computers to finish the test a month before the main person > > does in hopes of getting the prize. > > I think that the new licence could stop people from doing this, or could > quickly be altered to say so, as I assume that a new version would need to > be bought out to support it possibly... or at least make it easier... Surely this isn't really an issue. PrimeNet would surely recognise a result submitted by a "poacher" as such & either disqualify it automatically, or credit the actual owner of the assignment instead of the "poacher". > > In my personal opinion, the best way of doing this would be to set up 3 > computers in a 'loop' all doing the same exponent. Then they could > communicate at regular intervals. Although it would mean working at the > slowest speed, it might be a good idea to, along with backing up, get the > to cmpare exponents at the same time. This would fix the problem of one of > them quitting, another could be 'bought in', and also would allow > double=checking as the check went along. However, I suspect the > programming would be quite difficult..... Actually, it's not too hard. I suggested an algorithm which works very similarly to this & submitted it several months ago. I think the _real_ problem with a "partial results bank" is that it might be possible for double-checkers to "cheat" by starting from a late intermediate save file (unscramble the whole residual, pick a different offset & re-write, start the run from there & get credit for running a whole double-check). For this reason I'd suggest that such a "results bank" be public write only. This would also make it useless to individuals who might wish to use PrimeNet's filestore for nefarious & possibly illegal purposes, like distributing pornography. PrimeNet could mail the intermediate save file to the individual user concerned when (s)he was given the assignment to complete the run on that exponent. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 23:15:43 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: splitting up 10m digit primes On 14 Oct 99, at 18:37, Jukka Santala wrote: > Personally, I think the big problem with regards to this is not people > quitting so much as the possibility of major hard-drive failure etc. on the > testers. I doubt many of them keep good backups NO EXCUSE! A Zip drive or a CD-R is inexpensive and effective; one will service many networked systems, they don't all have to be running the same OS. > (And the client is supposed to run undisturbed, anyway) ? I thought the client was designed to run in the background to the user's normal activity. To me, that includes running backups. In any case, I can't see what harm there is to the client in copying the save files (also results.txt and the various ini & log files). The client usually doesn't have these files open. If you have a save file open for copying at the instant the client tries to write it then the file rename will fail & you'll lose writing the save file on that particular occasion. It's unlikely, but you _might_ lose an extra half hour's work if your system happens to go belly up in the interval before it tries to write the save files again. > and with a test taking anywhere from year to two > it's bound to become an increasily common experience for somebody's > hard-drive to give up the ghost, or an error/virus wipe the drive clean, and > the person running the test not only lose the work but probably take their > anger out on PrimeNet once they learn there's no way to recover the work. I get the impression that hard drives are becoming increasingly reliable. And virus infestations are very often not as destructive as all that, it's usually possible to recover data. The most frequent cause of data loss, by far, is the user accidentally deleting their own data. If this happened to me, and I didn't have a backup, I'd have only myself to blame. And, personally, I'd be more concerned about lost data that I couldn't recompute in _any_ finite time. If it _really_ worries us that PrimeNet might get "blamed" for data loss, let's put a clause in the PrimeNet "rules" to the effect that users are personally responsible for the security and integrity of GIMPS/PrimeNet data on which they're working. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 18:38:26 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: The Mysterious Ways of S.T.L. > <<Suppose M(x) is the number of primes p <= x for which 2^p - 1 is prime.... > Lenstra, Pomerance, and Wagstaff all believe this [an early conjecture by > Gillies] and in fact suggest that ?? M(x) ~ e^gamma log x ?? where the log > is to base 2.>> > Hence, my new conjecture: > ?? M(x) ~ e^gamma log[2] (x) + C ?? > > Of course, I used 1.4615 to make my 3 conjectures to the Mersenne mailing > list. In reality, I'm guessing it might be 1.5, or even 2^(1/e^gamma)! (In > fact, I'd rather go with 2^(1/e^gamma), as Erhardt chose 1.5 for the e^gamma > in the conjecture and now several mathematicians call the Erhardt Conjecture I'm afraid that if you are correct, so is Wagstaff. The symbol "~", at least in mathematics means that if f(x)~g(x) then f(x)/g(x)=1 as x->infinity. Your conjecture seems like it would yeild a better aproximation than Wagstaff's (you could certainly argue that 2 is a special case, since it's corresponding Mersenne is the next bloody prime, and there is 1 of the 1.4615 right there). - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 19:44:06 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: splitting up 10m digit primes > > Personally, I think the big problem with regards to this is not people > > quitting so much as the possibility of major hard-drive failure etc. on the > > testers. I doubt many of them keep good backups > > NO EXCUSE! A Zip drive or a CD-R is inexpensive and effective; one > will service many networked systems, they don't all have to be > running the same OS. True, also Pkzip 2.04g (I don't know about WinZip) had the ability to span a zip archive across floppy disks. Even on a LL test of 33mil would take up under 3 floppies. (This wouldn't be reasonable for large networks, but it would be easily achievable for the home user...) - -Lucas _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 20:32:45 EDT From: [EMAIL PROTECTED] Subject: Mersenne: Approximate! <<I'm afraid that if you are correct, so is Wagstaff. The symbol "~", at least in mathematics means that if f(x)~g(x) then f(x)/g(x)=1 as x->infinity.>> So constants don't matter, of course. <<Your conjecture seems like it would yeild a better aproximation than Wagstaff's >> Nod, that's what I was aiming for. I wasn't trying to prove Wagstaff wrong - just find a closer way to estimate M(x). At least the ~ means that adding a constant doesn't change f(x)/g(x) = 1 as x -> infinity... right? (See, if something turns out to be faulty in the way I made my conjecture, that paper I mentioned will be a lot weaker.) S. "Glad he kept a scribbed piece of notebook paper so he could remember how he made his conjecture in the first place" L. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 19:51:47 -0700 From: "John R Pierce" <[EMAIL PROTECTED]> Subject: Re: Mersenne: DOSville > >> Linux is smarter -- it automaticaly gives preference for the last CPU > >> used, without any special settings. Sometimes, however, if for some > >> reason the kernel or other threads need that specific CPU, Linux will > >> move the process. You win. > > Actually, NT does the same thing. > > Nope. You set the affinity to CPU 0, 1, etc. The process will then > _only_ run on that specific CPU. Right. But if you DON"T specify affinity, it does something very much like what you described linux as doing. > > >>... > > have you actually tested this? > > Start Prime95 at idle priority with CPU affinity set to one of the CPUs. > Start the "Tast Manager", choose "Performance" and look at the graphs. > One should be at 100%, the other close to 0%. Then start another process > at normal priority and see how the load of that process divides between > the CPUs, leaving one 50% idle while Prime95 stays on the single CPU it > has set affinity to (the other). I tried this on a Windows NT 4.00.1381 > Service Pack 3 Terminal Server. well, on a regular (non-TSE) NT 4 Server (service pack 4) dual PPro-200, I ran two instances of prime95, and gave one explicit affinity, and the other I left default ('run on any CPU'). Guess what? Both CPU's remained 100% busy, and both instances of prime95 got 49-50% of the total (per the process monitor in taskmgr.exe). This implies to me that it is clever enough to ALWAYS run the 'floating' process on the free CPU and leave the affined CPU to the affined process. Maybe TSE (Terminal Server Edition) has way different heuristics, I dunno. - -jrp _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Oct 1999 06:27:24 +0300 From: Jukka Santala <[EMAIL PROTECTED]> Subject: Mersenne: Re: Reliability (was Re: splitting up 10m digit primes) + Possible Wish List item Joth Tupper wrote: > The size of the files is an issue. With interim result files in the 7MB to > 10MB range, some ISPs just cannot handle the size. We're talking about "the program" here, there's no reason to stick with e-mail - and in fact it's just an encumbrance. (Well, beyond that being simpler and more easily avilable, but still...;). As for your bandwidth-concerns in general, this is (among other obivious things!) why I said the option to act as backup should be one more selection in the config. If you can afford the bandwidth and storage space, you can check the box. I guess now you'd have to add another box to select between e-mail and "direct" connect, which would be far more efficient and straightforward, but require both clients online at the same time and no firewalls. Then people with ADSL or T-1 could offer their storage-space for the project. People uploading even 10 megs over 56k modem once in a world wouldn't be too much for many people (Myself included, even though I need to pay for time online) to know their work is secure. So I guess I should get into work coding this ;) -Donwulff _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Oct 1999 07:15:51 +0300 From: Jukka Santala <[EMAIL PROTECTED]> Subject: Re: Mersenne: The Mysterious Ways of S.T.L. [EMAIL PROTECTED] wrote: > Hello, everybody. As usual I'm quoting different people. Disturbingly, I > noticed a weird HTML tag on my last E-mail. I can assure you I didn't put it > there, and don't know why my software's acting up on me (because I've never > seen that jibberish before). HTML mail is evil, only second to MIME. Long > live ASCII! Please excuse my delay in sending this message. I'm going to play clueless here, and without so much as a scientific reasoning note that since "we all know" composite exponents can't yield a Mersenne prime... is it somehow possible to "factor" this into any estimate on where the next Mersenne prime is? The most obivious way to play with this would seem to be to deal with a set of only the prime Mersenne exponents for the statistical play. However, I'm going to leave that for somebody else to dissect and blow apart as to why it wouldn't work, or try out on their statistical software. Other thoughts are trying the statistical approach either on the exponent itself, or the length of the whole expanded number, both within the set of all Mersenne numbers and only Mersenne numbers with prime exponents. And see if any patterns turn up. Okay, so admittedly this is just shooting in the blind, but I thought that's what prime-searching was about ;) (Personally, I don't believe there's any predictability to them) -Donwulff _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Oct 1999 07:19:32 +0300 From: Jukka Santala <[EMAIL PROTECTED]> Subject: Re: Mersenne: Islands of Truth Darxus wrote: > I've put a graph of these "pairs" up on my web page. > http://www.op.net/~darxus/p_pairs.bmp Never use BMP on the WWW, please! There's no way for me to look at that. -Donwulff _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Oct 1999 07:35:48 +0300 From: Jukka Santala <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: splitting up 10m digit primes "Brian J. Beesley" wrote: > On 14 Oct 99, at 18:15, Chris Jefferson wrote: > Surely this isn't really an issue. PrimeNet would surely recognise a > result submitted by a "poacher" as such & either disqualify it > automatically, or credit the actual owner of the assignment instead > of the "poacher". Except that PrimeNet doesn't control the prize. This is the error everybody is doing. EFF is adminstrating the competition and prize, given by anonymous donaters to advance distributed computing / mathemathical algorithms on computers. PrimeNet is just one of the organizations (With largest changes known!) to get that prize, but it doesn't decide upon who gets it. The first person to present a prime filling the requirements will - and that's why result-files "few iterations short" will be worth more than their weight in gold. Somebody else said: Users _should_ backup etc. Well, you've all already seen how people "blame" GIMPS for having .txt documentation and no nifty user-interface. You think the backup-issue will be any different? My reference to Prime95/mprime being "no maintenance"... At the worst case you're dealing with a thousand machines crunching away with assignemts got off the net, and sent back. How and where are you going to backup all that data? Assuming there's automatic backup, fine... but let's face it, most "personal computer owners" whom form the majority of GIMPS users I'm sure _don't_ make backups even of their other data. You said... about making the repository write-only. And you seem to completely miss the point; the discussion here has centered around how to solve the problem that PrimeNet doesn't have the bandwidth or storage space to backup the intermediary files! So my suggestion was "distributed storage". This will solve the backup problem, but yes the above-mentioned prize-claim and double-check problem remains. Unfortunately, I think in that respect we're stuck. -Donwulff _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 15 Oct 1999 23:18:09 -0700 From: "John R Pierce" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Islands of Truth > Darxus wrote: > > > I've put a graph of these "pairs" up on my web page. > > http://www.op.net/~darxus/p_pairs.bmp > > Never use BMP on the WWW, please! > There's no way for me to look at that. here, I whacked it for you... http://hogranch.com/files/Bitmaps/p_pairs.gif since it was a very-few color chart, GIF was the logical format. BMP was 71k. GIF is 4K. nuff said? - -jrp _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Oct 1999 02:22:38 -0700 From: Greg Hewgill <[EMAIL PROTECTED]> Subject: Re: Mersenne: Smallest unfactored composite (was types of work to request...) On Fri, Oct 15, 1999 at 01:03:57AM -0800, Gordon Bower wrote: > PS - On an unrelated note --- what is the smallest natural number that is > not known whether it is prime or composite? Surely *someone* out there is > trying to work from the bottom up and factor every number. (I don't know > the answer. I am guessing the it is a smallish number of maybe 15 or > so decimal digits?) Suppose you were keeping such a list. With one bit (prime vs not-prime) to represent each number up to 10^15, you would need approximately 10^14 bytes of storage, which is on the order of 100 terabytes. That would be your first problem. The second problem would be if you were to present me with the smallest number that was not factored, I could almost immediately present you with a factorization (or show that it's prime). The point is there are so many numbers, it would take far too much time to determine the character of even the small ones that could individually be characterized almost immediately. Here's another argument - suppose the largest unfactored composite was C. How long did it take to determine the factorization (or primality) of C-2? (C-1 would be even.) Then to factor C would only take a marginally longer amount of time than it took for C-2. There is no reason you could not complete the factorization of C. Greg Hewgill _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Oct 1999 12:54:55 +0200 (MET DST) From: [EMAIL PROTECTED] Subject: Re: Mersenne: Smallest unfactored composite (was types of work to request...) On Fri, Oct 15, 1999 at 01:03:57AM -0800, Gordon Bower wrote: > Here's another argument - suppose the largest unfactored composite was C. How > long did it take to determine the factorization (or primality) of C-2? (C-1 > would be even.) Then to factor C would only take a marginally longer amount of > time than it took for C-2. There is no reason you could not complete the > factorization of C. Alas, if Gordon's argument is valid, then every positive integer would be factored. This is the principle of mathematical induction. A computer may be in a loop. It has factored C-2 and C-1, and is now working on C. The task of factoring C may indeed take only marginally longer than it took for C-2, but the extra time is nonetheless positive. The next number may be factored as you read this paragraph, so a journal article saying "Every number below this C has been factored, but C itself has not been" would become outdated almost immediately, even if true when submitted. We can use the same argument on how much water our bodies will hold, or how much pollution to allow. At any given time, adding a single molecule may seem safe. But the capacities are finite. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Oct 1999 15:46:30 +0100 (BST) From: Chris Jefferson <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: splitting up 10m digit primes On Sat, 16 Oct 1999, Jukka Santala wrote: > "Brian J. Beesley" wrote: > > > On 14 Oct 99, at 18:15, Chris Jefferson wrote: > > Surely this isn't really an issue. PrimeNet would surely recognise a > > result submitted by a "poacher" as such & either disqualify it > > automatically, or credit the actual owner of the assignment instead > > of the "poacher". > > Except that PrimeNet doesn't control the prize. This is the error everybody is doing. > EFF is adminstrating the competition and prize, given by anonymous donaters to > advance distributed computing / mathemathical algorithms on computers. PrimeNet is > just one of the organizations (With largest changes known!) to get that prize, but it > doesn't decide upon who gets it. The first person to present a prime filling the > requirements will - and that's why result-files "few iterations short" will be worth > more than their weight in gold. > Yes, but the licence for Prim95/NT specifies that anyone who uses this program must obey it's licence. Someone using a partly completed file would also be liable under this. However, proving that they has used the interim file generated by this particular program might be difficult... _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Oct 1999 15:56:41 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: splitting up 10m digit primes On 16 Oct 99, at 7:35, Jukka Santala wrote: > [ ... snip ... ] > Except that PrimeNet doesn't control the prize. This is the error everybody is doing. > EFF is adminstrating the competition and prize, given by anonymous donaters to > advance distributed computing / mathemathical algorithms on computers. PrimeNet is > just one of the organizations (With largest changes known!) to get that prize, but it > doesn't decide upon who gets it. The first person to present a prime filling the > requirements will - and that's why result-files "few iterations short" will be worth > more than their weight in gold. I think, if someone tried to pull this particular stunt, PrimeNet could inform EFF of the claimant's theft of the right to the discovery (which is what it amounts to). Another unfortunate example of the way in which large ca$h prizes can lead to unpleasantries, I'm afraid. > > You said... about making the repository write-only. And you seem to completely miss > the point; the discussion here has centered around how to solve the problem that > PrimeNet doesn't have the bandwidth or storage space to backup the intermediary > files! So my suggestion was "distributed storage". This will solve the backup > problem, but yes the above-mentioned prize-claim and double-check problem remains. > Unfortunately, I think in that respect we're stuck. Well, I sort of _did_ miss that particular point. But I have a solution. If you have a distributed filestore, controlled by a number of different people, then you encrypt & hack up the file you're saving and scatter pieces amongst the remote filestores. If you (the assignment owner) use a method based on a key otherwise known only to PrimeNet to scramble & scatter the file, the small chunk of data stored on any other individual's system is useless to them for the purposes of hijacking your work. I think PrimeNet should know users' keys so that data can be recovered in the event of the user defaulting or accidentally destroying their own key (so that work done isn't lost). Presumably we trust the people running PrimeNet! An obvious extension to this idea is to use a RAID type technique e.g. if you store each bit of a byte on a seperate host, so that the file is scattered over 8 hosts, you could send the parity bit to a ninth host. Then the distributed filestore is immune to loss of one of its hosts (by reason of network failure or unsecured loss of its filestore). As for bandwidth and total filestore space needed - the first is, and will probably remain for some time, a problem, at least for most home users. 10,000 x 8 Mbyte save files is a lot of data by today's standards; nevertheless, 4 20GB drives at $200 each would just about cover it. (A random dip into a UK magazine shows Samsung 20.3GB UDMA66 IDE at �144 (sterling) each, so US$10 per GB should be achievable) Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 16 Oct 1999 15:56:41 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Re: Mersenne: The Mysterious Ways of S.T.L. On 16 Oct 99, at 7:15, Jukka Santala wrote: > I'm going to play clueless here, and without so much as a scientific reasoning > note that since "we all know" composite exponents can't yield a Mersenne prime... > is it somehow possible to "factor" this into any estimate on where the next > Mersenne prime is? The most obivious way to play with this would seem to be to > deal with a set of only the prime Mersenne exponents for the statistical play. > However, I'm going to leave that for somebody else to dissect and blow apart as > to why it wouldn't work, or try out on their statistical software. Other thoughts > are trying the statistical approach either on the exponent itself, or the length > of the whole expanded number, both within the set of all Mersenne numbers and > only Mersenne numbers with prime exponents. And see if any patterns turn up. They will, and they're very likely to be artificial. You can analyse results of tossing a coin all you like; eventually, you will find some trend which is statistically significant - even if the coin really is fair. Knowledge of this trend will not help you one iota in predicting the outcome of the next toss of the same coin. If you could find something like "it's not worth trying exponents congruent to 21 mod 22" from analysis of existing known Mersenne primes, chances are that you'd be wrong; we just haven't found any yet, our sample size being painfully small. However, it might be worth putting a little effort into a mathematical argument as to why the conjecture might be valid. Note - the conjecture above may well have at least one known counterexample - it's just an example, I didn't bother checking it! Regards Brian Beesley _________________________________________________________________ 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 #645 ******************************
