Re: Mersenne: Re: PNG (good!)
Version Visitors % 1. MSIE 5.x1,70553.26 2. Netscape 4.x1,17336.63 3. MSIE 4.x2247.00 4. MSIE 5.x (AOL)541.69 5. Netscape 3.x120.37 6. MSIE 3.x100.31 7. Netscape 5.x80.25 8. MSIE 4.x (AOL)50.16 9. MSIE 2.x40.12 10. MSIE 3.x (AOL)40.12 11. Opera 3.x20.06 12. Opera 2.x10.03 Total 3,202 100.00% Apparently broken statistics, since at least one of the browsers I regularly visit with isn't represented. If you are referring to Lynx, then it may be that Lynx has deceived the webserver. If I recall correctly Lynx (at least of a few versions ago) told webservers that it was netscape to avoid the server not sending the page. Possibly, anyway... -Lucas Send your favorite photo with any online greeting! http://www.whowhere.lycos.com/redirects/americangreetings.rdct _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Re: Mersenne: pi
At 10:50 AM 2/9/00 -0500, Jeff Woods wrote: You're bumping up against the Fundamental Theorem of Calculus here. Pi DOES have a precisely defined value, but you cannot express it in decimal form. You can express it as an infinite expansion, however. Q: What does this have to do with fundamental theorem of calculus? The fundamental theorem equates anti-derivitives with area. This has more to do with the proof that there are numbers which cannot be expressed as the ratio of integers (i.e. irrational numbers) due originally to pythagroeus (SP), as well as the proof of the irrationality of pi (due to Newton, I think). The first is proved *long* before the fundamental theorem, and is in some ways more fundamental. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: P-1 factoring
Will this P-1 factoring step take place ONLY before a LL test, or will it also be part of the trial factoring step? The reason why I'm asking is because one of my machines is a dedicated 486 to work on trial factoring only. It has 16MB RAM. The hard disk is *very* slow, so when it thrashes, my 486 is essentially rendered useless. The P-1 step would become a fourth work assignment (to be done after a number has been trial factored, but before it has had an LL test run on it). Much like how the trial factoring and LL test are done on separate computers. -Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re : Odd's on finding a factor (part 2)
Thus for the exponent 1165 bits long, if it only has 2 factors , then the first factor must be between 2 and 3413 bits long, and the second factor must be between 3413 and 1164 bits long. Note that the bit lengths of the 2 factors added together must equal the bit length of the Prime (or bit length of the Prime + 1) !! No, if the exponent=1165 (I think this is what you mean), the mersenne number must be this number of bits (as you know). The first factor must be less than sqrt(M_p), not M_(sqrt(p)), which is what you were doing. The first factor must therefore be less than 2^(p/2)=2^58250002^sqrt(1165)~=2^3413. You would probably get better results with Will Edgington's mersfacgmp program, and DJGPP (a port of g++ to dos). I'll check it out. I'm using UBASIC because for testing factors of large Mersenne, I don't need to actually represent the full Mersenne Prime. If you're familiar with UBASIC try ... Result = MODPOW(2,MersenneExponent,TrialFactor) where TrialFactor is the MersenneExponent * 2 * (some k in range 1 to 2^16) + 1. If Result = 1 then TrialFactor divides the Mersenne Prime. As UBASIC can handle around 2600 decimal digits, in theory (and with a lot of time), I could check all factors up to 2600 decimal digits for any given exponent. It's a damn sight faster than filling 16MB+ of memory with 1's and then trial dividing. Will's program does this also (see Knuth volume II (I think 4.5.3, but I'm not sure don't have my copy handy), or the mersenne FAQ at the bottom of this message). Thinking on it in a slightly more awake state, I'm not sure how much faster it would be, but try it anyway. You will need to download DJGPP (search altavista for DJGPP), set it up, compile the GMP library (ftp://metalab.unc.edu/gnu/gmp (I think), there is a dos batch file), and compile Will's program (I think it is in the links section of the mailling list FAQ). But, under windows, would George's program be the fastest (or are you using very large exponents?) Have fun, Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Q:GIMPS freezes my system
Hi there, I've experienced a problem. I'm wondering if anyone else has had this problem: GIMPS freezes my system after it runs for about 24 hours or so. I have Windows NT 4.0 (SP5) Dual Intel Celeron 433Mhz (BP6 motherboard) 128MB RAM If I quit both GIMPS processes on my machine (and I'm running one with the -A2 command-line option) and start them again, no problems. It's only after both have been running for some time. But I don't want to do this because I leave my computer for days at a time. It sounds like you might have problems with overheating in the case which can often cause lockups, since Prime95 stresses the CPU more, it produces more heat. I would advise getting a case fan. Just my $0.00 (the GNU version) -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: Odds on finding a factor
Who needs to? I have code which tries any number up to 2^95 as a factor of a Mersenne number with an exponent up to approx. 600 million, using less than 1 KByte of code space and 32 bytes of data storage. It executes in a time proportional to the logarithm of the exponent - for an exponent around 35 million, it takes approximately 2000 CPU clocks i.e. 4 microseconds per test on a 500 MHz CPU. This is a bit misleading, more accuratly, it runs in time proportional to lg(p)*lg^2(n), where p is the exponent, and n is the potential factor. Just call me "Mr. Pedantic". :) -Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Size of largest prime factor
But (assuming n is composite) no prime factor of n can be greater than n^0.5. So how can n^0.6065 be the average? (I hope I'm not showing my idiocy here! :) No, that's not correct. If n is composite, then it *must have* a prime factor n^.5, but it can (though not always) have one larger e.g. 217=7*31 sqrt(217)~=14.737, but 3114.73. -Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Re: Mersenne: Odds on finding a factor ?
If you're factoring numbers in the 1165-1166 (bit) range, the first factor could be anywhere in the root(1165) - root(1166) range i.e. 3413 - 3414 bits long !! No, in the x-y bit range (remember that n bit integers are about 2^n) the first factor could be x/2 to y/2 bits long (powers of a power multiply). I'd have thought your odds of finding a factor are a lot smaller than 12 / 64 - probably closer to 12/3361 - and that's only if we pretend that the power series 2^n is a linear series he he he. see http://www.utm.edu/research/primes/glossary/MertensTheorem.html Ala UBASIC, I estimate your real odds might be 4096 / 3298942664324070148398699377093587963271453646320083409970227900099032340084550 [...] Abreviate! Use scientific notation... Sorry to be the Grim Reaper, but I've spent months with UBASIC eliminating factors in the 32,000,000 to 48,000,000 range - I'm only on about 24% eliminated using multiples 2pk+1 where k is 1 to 2^16 - and there's no doubt that the density of factors decreases as the multiplier increases. Finding the first few % is easy - finding the last 1% might take forever !! Why are you only setting k==1 mod 2^16? (I'm probably missing something obvious) I think under windows that dos windows only run when they are "up". (I could be wrong, I've stopped using windows again) You would probably get better results with Will Edgington's mersfacgmp program, and DJGPP (a port of g++ to dos). -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: questions
why is f(0) in an ll test = 4 Well, it needn't be. There are a number of other possibilities, but 4 is the smallest... also when i went to sshool (i'm 34) 7 mod 8 == 7 i have seen 7 mod 8 == -1 is -1 == 7 mod 8 which is more correct They are both correct. If you have a congruence relation (mod n), then you can add n to either side (it's like adding or subtracting zero). -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: v17 double checking
Now that double checking has surpassed exponent 4194304, what happens to all those machines out there running the old v17 that produced incorrect results for LL tests above that exponent? (I don't have any, but they almost certainly exist.) Up to this point they will have been successfully doing double checking LL tests. Now they will be producing incorrect double checking results. Perhaps they should be given factoring assignments by the Primenet server? I'm guessing so... Of course they will eventually run out too, then we will either have to admit that these computers are now basically worthless to us (unless there is some way to reach them), or just try and give them some kind of error from primenet (?). Perhaps if there were some way to give an error like: Primenet error 1221: Invalid assignment "IMPORTANT: SEE http://entropia.com/important.html" -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Meganet Corp.
I may have missed this, but was there any final judgment on the Meganet Corp. claim that they had a "deterministic and polynomial-time" prime test? There were some discussions on the list early this year when they first made their claim. But I don't recall reading about any resolution. Did this just fade away? Are they still holding to their claim? And if they are, does it stand up to examination (if they are revealing enough for examination)? These guys are snake-oil vendors. I don't know what type of prime test they are claiming to have or not have but from my exposure to their crypto claims I wouldn't trust anything from them without proof. I'd say this is true in this case as well. On their site they say things like: Those results are unheard of. The 1,000 bits test on a Sparc II workstation takes 5 Minutes and it is still only PROBABALISTIC. The gap in time is much greater for larger bit sizes. Eh? The probable prime test on 10^999+7 took ~20 seconds on my PII/233. That's a thousand digits, ~3000 bits. (w/primeform) The major breakthrough is solving a 400 year old mathematical problem how to positively identify a prime number without spending exponential time in dividing the number by all the primes up to its root. This problem was solved by a primality testing algorithm that is based on eliptic curves (it was not practical), but it was polynomial. The solution Meganet Corporation have developed is based on a newly designed Mathematical Sequence called the T-Sequence. Once a number is transformed to the T-Sequence, its quadratic residue has definitive characteristics if its a prime number that can be easily determined in polynomial time by performing a binary decomposition. Ok, if it is a prime then a^p==a mod p, what's your point? They don't even give a correct statment for their claims, they should say if and only if... Meganet Corporation would like to emphasize that there is a 100% mathematical proof behind their T-Sequence, and further, it is a complete working product tested successfully on over 1.3 million numbers without a single mistake. Ok, so proofs are measured in percent? Also, how many numbers are both a 2-spsp, and a lucas psuedoprime ($620 prize). I'll bet that that combination has been tested for a lot more than 1.3 million numbers without failure... Besides, the name meganet is too remanisant of Homer simpson's name for his internet company (on the Simpsons) I believe he called it something like hyper-compu-global-meganet. (It was eventually bought out by bill gates for fear of competition). -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Trial-factorers
Well, I'm prepared to have a go. Could we tighten up the spec a bit? (a) There's also been some interest in something else that Prime95 doesn't do - trial factoring 2^p+1. (Note that this form also form also has factors of the form k*p+1.) (b) I assume we're only interested in 2kp+1 factors. This means that we will miss any factors which are not of this form. (Applies to Mersenne numbers with composite exponents, and all 2^p+1 numbers - though I believe that the "missed" exponents are easy to derive analytically.) Yes, those mersenne numbers with composite exponents have factors of the form 2^d-1 where d|p, but the remaining unfactored portion must have factors of the form k*p+1. (I believe that is Legendre's theorem) (or rather a consequence of it) It's probably sensible to go for an application which runs in a "DOS box" rather than a proper windowed application. This makes it a bit easier (for me) to write also makes deriving a linux variant almost trivial. (Does anyone know for sure whether or not there's a DOS box in "Millenium"? I heard a nasty rumour...) Egad! If true then it would be added to the long list of complaints I have with microsoft. If we can agree on that, then I have a basis to begin coding. Will certainly take a month or two to produce even a pre-pre-release as I am very pushed for time at the moment. No need to rush, I wouldn't call the need for such a program urgent. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: MersenneInfo: What Happened?
To The MBase: Haven't received any forwards since Friday Oct. 29th... I believe the problem lies at the source. I don't think that anybody has been sending mail to [EMAIL PROTECTED] -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: Schlagobers, Louisville style
But while watching the movie Pi, it occurred to me that since the number Pi has *nothing* to do with base 10, there would be no repitition in the digits in any approximation of it in base 10 (or any other integer base, for that matter). The sequence of digits *should* be completely random, and it's goofy for people to try to look for patterns. I mean hey, if it's what you gotta do, go for it, but I think time would be better spent on other things. Yech! To maintain the niceties of the list, I'll just say that I'm not a fan of that movie. I remember some notes on interesting patterns in Pi that led one to believe that certain statistical events were NOT ocurring. For example, in a completely random set of (base 10) digits, one would expect a string of, say, 100 of the SAME digit to appear in the first so many digits of the number, however this doesn't happen in Pi and, furthermore, certain digits appear in large clusters more often than others in the list of 'known' digits. Umm, would the probability of any specific series of n digits in a random sample occurring be 10^-n? This shouldn't yeild a series of a hundred of the same digits for some time, if the sample is random. Does anyone have any stats on this? Personally, I imagine this is the same sort of statistical dribble as "The Bible Code", and someone probably got their Chi-squareds mixed up when they were doing the math, but since I'm not strong in statistics, it would be nice to hear an 'Expert' opinion. You mean the bible code isn't real, I'm shocked... -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Reciting Mersennes...
Noone could call their full decimal name in a life time, allthough it is finite in length. If I remember correctly, someone once recited millions of digits of Pi from memory in three days. Heh. You probably don't :). I believe the world record was around 40,000 digits. I find it highly unlikely that a human brain could hold that many digits. Even assuming reciting 3 digits per second, that would take 3.85 days, no sleep. I agree with Preda that these numbers are "abstract". They are completely unimaginable in terms of size, yet completely handlable thanks to mathematics. This is probably why people find them so fascinating. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: estimating mersenne primes
I was pretty surprised that the extrapolations for M38-M42 (all that I did) were *exactly* the same for both methods of extrapolations, Your two methods are equivalent. I know, but I thought the algorhythms for fitting linear exponential lines would differ enough to result in at least a small difference in results. I believe the first thing to do in finding an exponential curve fit is to take the log of the data, then apply a linear fit. (?) That is how I would do it anyway. This would produce identical results to the accuracy of the logarithm. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: The Mysterious Ways of S.T.L.
According to the "Where is the next larger Mersenne prime?" page -- http://www.utm.edu/research/primes/notes/faq/NextMersenne.html the Wagstaff conjecture suggests a slope of 3/2, which I believe wouldn't look so bad. No. Wagstaff's conjecture predicts a slope of around 1.47, (2^exp(-Gamma)). I would really like to try your calculations myself, but I haven't seen my graphing calculator for a while, I'm not sure it'd work, and I'd prefer to use the power of my computer. Can anybody suggest any programs ? Preferably for Linux, even though that would mean I'd have to wait to get my Linux drive back. GNU plot (I've never had a need to use it, but I've heard good things about it). I know that it comes with Redhat and Debian. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Bold Predictions From STL's Mysterious Ways
STL: what was the line you fit to the log log of the known mersenne's exponents, and what was the error (r^2) ? I'm assuming r^2 is like, the amount of error for a given line fitting a set of data. When I fit an exponential line to the 1st 37 mersenne prime's exponents (since I believe that 6972593 is actually the 39th, but have no proof, so I figured I'd leave it out), the line I got was y=1.7661e^0.301x (hope I wrote that right), and r^2=0.9925. I have a feeling the log log thing will actually be more useful.. easier to predict a straight line than an exponential curve. They are actually equally easy to predict. A straight line is just a log of an exponential curve. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
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
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
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
Re: Mersenne: DOSville
.TXT files are the one true document file. Pure ASCII bring it on!
Mathematical notation in .TXT isn't easy, though. It's a conspiracy.
It works well enough. Most of it is pretty standard, and TeX fills in
the rest
$$\int_{0}^{1}\sqrt{1-x^2}dx={\pi \over 4}$$
Yeah!
FOR GOD SAKE GIVE ME A USER FRIENDLY INTERFACE, PROPER HELP MENU
Give me a DOS-based command line (yet Win98 background-running capability)
with a really nasty, God-awful set of fifteen switches that must be ordered
in a precise way depending on the phase of the moon. :-P
Sorry, but M$ didn't invent multitasking, and from what I've seen
(I haven't seen NT multitask much) they have yet to implement it effectivly.
BTW, if you love command line programs with obscure switches, you could
try Linux.
S. "Property of Billy and Andy" L.
-Lucas "I owe Linus a case of beer by now" Wiman
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: # of digits in 2^p-1
What's the best way of finding the number of decimal digits for the number 2^p-1 ? Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ^^^ ^^ Q5.3. It's no good unless people read it! -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: estimating primes (was: Re: Mersenne: Islands of Truth)
Hmm... I just changed my worktodo.ini to Test=5014947,63 (where's the 63 come from ? it was used for the last number I was assigned). It's saying "Error: Work-to-do file contained composite exponent: 5014947" I suppose that means it's already been tested found to be non-prime ? (composite = non-prime, right?) This is for the number of bits the Mersenne number has been trial factored to. I.E. your last number was factored to 2^63. the reason that it reported a problem was that the exponent was composite. This means that the corisponding Mersenne number is composite, thus we only check prime exponents. The number 5014947=3*7*47*5081. Thus 2^3-1, 2^7-1, 2^47-1, and 2^5081-1 all divide 2^5014947-1 (though they do not factor it completely!). -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: splitting up 10m digit primes
There is now a prize for factoring Fermat numbers too. Neat. Where's the info ? I think Richard Crandall is offering a prize for Fermat factors (http://www.perfsci.com). John Selfridge is also anouncing a prize for factors of various numbers which "ought to be prime". I don't think that there is a website yet. I'll repost the list if you are interested. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: probability of primeness (was: Re: Mersenne: splitting up 10m digit primes)
I think trial factoring is done to 2^68 for an exponent around 33 million. Thus your chance is 2 * 68 / 3300. Okay, so as far as we know, each number is equally likely to be prime, and this probability is just based on how much has already been tested ? Umm, no. The probability that a number is prime is inversly proportional to the number of digits (or more precisely, the probability that a number on the interval [1,x] is prime is asomtotically 1/ln(x)). However, the probability that a number is prime increases with the amount that has been trial factored (without finding a factor). The precise estimation is based on Mertel's theorem. Ugh... I apparently had bad math teachers, and GIMPS is really making me feel it. I *really* wanna play with these numbers, but I feel intellectually cripled. You certainly seem to have done a good job! You found the two big conjectures about Mersenne distribution. That is Curt Noll's (poorly defined) island theory (your pairs observation), and your observation about it being roughly exponetial (a conjecture due to Wagstaff, and others, though Wagstaff's has hueristic evidence to back it up). I took the numbers from http://www.utm.edu/research/primes/mersenne.shtml#known See http://www.utm.edu/research/primes/notes/faq/NextMersenne.html, as well as http://www.tasam.com/~lrwiman/FAQ-mers, Q4.2. Does anybody see what I'm talking about ? Is there any significance to this ? Has somebody already written extensive papers on this ? Yes, see above. Good work! -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: gzipped binary expansion of the largest prime
Is there a copy (preferably unformatted plaintext) of the decimal expansion of the largest (2million-some digits) prime, gzipped or zipped or something, somewhere ? Yes! Landon Curt Noll has all the Mersenne primes on his website. http://reality.sgi.com/chongo/prime/merdigit/index.html#largest (Ack! I'm slipping, I had to look it up!) Also (if you want it in poster form) look at www.perfsci.com (though last I checked it was ~$30 US). Bummer, calc didn't compile in my shell account. In file included from seed.c:53: /usr/include/sys/resource.h:25: field `ru_utime' has incomplete type /usr/include/sys/resource.h:26: field `ru_stime' has incomplete type seed.c: In function `pseudo_seed': seed.c:216: field `tp' has incomplete type seed.c:241: field `tp2' has incomplete type *** Error code 1 make: Fatal error: Command failed for target `seed.o' Oh well, hope my repaired Linux drive gets back soon Hmm, you might want to sent this to Noll. He is big on getting Calc to compile without errors on darn-near everything. Also look at Pari/GP. It has binaries for windows! (It seems faster than Calc too!) ftp://megrez.math.u-bordeaux.fr/pub/pari/windows (take off the /windows for linux/msdos/mac/etc versions). Hope this helps, Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Mersenne data repository
Anyone who has data which they wish to make publicly available may wish to take advantage of my FTP server. Downloads from the server are already available by anonymous FTP (ftp://lettuce.edsc.ulst.ac.uk/gimps), I keep copies of many Mersenne- related programs and also George's database files. We could put this on a domain name. mersenne.net is not taken, and I'm sure we could get the registration fee. I would certainly be interested since I probably won't be using tasam.com in a couple of months, and hence I need some place to host the FAQ. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM Factoring
I would like to look for a factor of a mersenne prime in a specific area. For example, for a mersenne exponent of say 40,000,000. I want to use the Prime95b program, (v19 I guess), to search for a factor in a specific range from, say, 2^40 to 2^50. I do not understand the ECM factoring instuctions included with Prime95. For this targeted a test, you might want to use trial factoring simply edit to worktodo.ini file adding the following line Factor=a,b Where a is the mersenne exponent, and 2^b is the limit trial factored to. you can override the default trial factoring depth with the line FactorOveride=n where n is the power of 2 that you want it to stop at. (I think that is how it is spelled, see undoc.txt) (a rather ironic title in my opinion) I don't understand how to set the ECM= paramaters to accomplish my goal. It is my understanding that one can use ECM or 2^p-1 factoring with V19. (I think you mean P-1 factoring). Yes, but ECM wouldn't be best for such a targeted search (as I understand it). -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM Factoring
When this is cleared up, it will make a good FAQ. Who maintains the FAQ list? Do you agree the answer here is a good FAQ? I would like to look for a factor of a mersenne prime in a specific area. For example, for a mersenne exponent of say 40,000,000. I want to use the Prime95b program, (v19 I guess), to search for a factor in a specific range from, say, 2^40 to 2^50. I do not understand the ECM factoring instuctions included with Prime95. I maintain the FAQ (well, one of three anyway). There is my FAQ which deals mostly with the math involved with Mersenne numbers. There is Scott's FAQ which deals with primenet, and there is George's FAQ which deals with Prime95. I have gotten questions involving all three (and at least 2 letters which assert mine as the "best"). I like the current separation for a number of reasons: (1) It makes sense (2) I know next to nothing about Prime95, and even less about primenet (3) I don't really care enough about the other two to put forth much effort. (Note that I *do* apreciate Prime95 and primenet, I just don't care much about specific issues with them). Now the last one might sound bad, but with school, I hardly have time to add anything I care about to the FAQ (there is a section on P-1 factoring, Q3.10 BTW). Hopefully this should explain things a bit. I will (eventually, once I read more on it) add a section to the FAQ about ECM, but Prime95 specific issues I know little about, and George would be much better suited to writing about this. Sorry if my rambling makes no sense... Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Graphical visualisation of computations
I must admit, I dallied (albeit very briefly) with the bovine rc5 client. Gack! About the only manufactured challenge comes from ID software. Should read About the only more manufactured challenge comes form ID software. :) -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: trial factoring using P-1's GCD
I've been wondering about this lately... If we are to begin P-1 testing on larger exponents, this implies lower trial factoring limits (though possibly only by 1 or 2 bits). Now, P-1 requires an investment of a GCD on two numbers each of similar size to Mn. So, since we are investing this much (computational) engery in a GCD, why not cram in as many factors as we can? Would it be possible to find multiply the (a^q-1) mod Mn by small (possible) factors skipped due to the lower factoring bounds faster than it would to directly check these possible factors? Gack, that was a bit unclear, say that k*n+1 divides Mn, k is non-B1-smooth. Which would take more time, checking (directly) to see if k*n+1 divides Mn, or multiplying (a^q-1) by k*n+1? (assuming k*n+1 is around 64 bits) Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factor of 2^(2^31-1)-1 found ($)
All (and especially Chris), Yesterday (and the day before), I went to the Illinois number theory conference. There (2nd talk of yesterday) J. P. Selfridge announced that he would give away $1000 US for any factor found of a number which ought to be prime (he provided a list). On that list was 2^(2^31-1)-1. Please post the list of candidates, to the mailing list. Ken F_m for m=14,20,22,24,31 M(M(p)) for p=31,61,127 M(B(p)) for p=31,61,127 F_m for m=2^k+k k=6 B(p)=(2^p+1)/3 -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factor of 2^(2^31-1)-1 found ($)
All (and especially Chris), Yesterday (and the day before), I went to the Illinois number theory conference. There (2nd talk of yesterday) J. P. Selfridge announced that he would give away $1000 US for any factor found of a number which ought to be prime (he provided a list). On that list was 2^(2^31-1)-1. I began searching for a factor of this number in mersfacgmp at around 12:10 Central standard time. I thought that mersfacgmp was malfunctioning, because it terminated too quickly, but I was wrong, it had found a factor! 295257526626031 divides 2^(2^31-1)-1, I have confirmed it in 3 different programs. Just to make sure that I haven't gone off the deep end, could Chris Caldwell confirm that he actually offered a prize for this number, and could the rest of you confirm that it is an actual factor? Also, Chris, I lost the sheet that had everyone's email address' at the conference, could you send me J.P. Selfridge's email address? Thank you, Lucas To guard against errors in transmitions the factor is 295257526626031 _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Re: Factor of 2^(2^31-1)-1 found ($
Oopsy. That should have read J. L. Selfridge -lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: M(M(127)) and other M(M(p))
Of course, the sequence that still remains unknown is 2 M(2)=3 M(3)=7 M(7)=127 M(127)=170141183460469231731687303715884105727 M(170141183460469231731687303715884105727)=??? Yes, this sequence is interesting, but if someone finds a way to prove/ disprove the primality of M(M(127)), I think that would be far more significant than actually proving/disproving that specific number prime. (Assuming you don't find a factor, that is). I checked Chris Caldwell's pages on this, and Curt Noll's trial-factored M(M(127)) to 5.10^50, surprisingly low considering the size of M(127) itself, I noticed many other M(M(p)) as listed in http://www.garlic.com/~wedgingt/MMPstats.txt have only been tested to very low limits indeed. The reason is relativly clear: the work of checking *even one* factor of M(M(p)) is greater than the work required for an LL test on that number. This is because of the need for p squarings modulo some number greater than M(p). I wondered why there wasn't more work done on these - though I understand it's very hard to motivate people when Guy's law of small numbers no doubt applies, but everything M(M(61)) and above is currently unknown. It would be nice to see a few more results there. I'm guessing that if a more optimized program were created, then perhaps there would be more interest. The Selfridge prize for these numbers could help. ...However, we have no way of knowing wether or not these numbers are prime, unless we find a factor. Interestingly enough, when we find the next Mersenne prime, searching for a factor of M(M(p)) might allow us to find an even bigger prime. If for example, 6*M(p)+1 divides M(M(p)), then it must be prime! Wait, that might just be the reason to search! Will only searched up to k=4 for M(M(6972593)), but if 2*k*M(p)+1 divides M(M(p)), then you've just beaten the world record! Non-Mersenne's might once again grace the top 10 list! -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: GIMPS client output
Might be nice to display the percentage out to an accuracy that changes every hundred iterations. Hmm, looks like that's an integer of the percentage, not rounded. Guess it doesn't matter. For the one I'm working on it looks like 3 decimal places would be needed to see a change every 100 iterations. This is changed in V19 (currently in Beta). I believe (George correct me if I'm wrong) that you can specify it up to 6 decimal places. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: P-1
But as everyone on this list knows, any factor of a Mersenne number looks like 2*k*p+1 for N=2^p-1. Plugging this into the above equation gives q=2*k*p+1 q-1=2*k*p Correct. Doesn't this mean the lower bound on a "p-1" method search should be greater that the Mersenne exponent (the p in 2^p-1) to have the best chance of success? Then the "upper bound" of the "p-1" search can be resevered for cracking a big factor in the "k" of a Mersenne factor. No. Simply multiply the exponent on the base by p. This produces the desired result, without having to go to the extra effort of extending the bound that far. I probably should add a section on P-1 to the FAQ. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Celerons vs. Pentium II/III at large FFT lengths?
Ackk! That was rather inexact wording. Let me try again...my Celeron 400 based systems crunch exponents in the 384K FFT range at about the same speed as George's PII-400 machine. However, at the 448K FFT size, George's machine appears to be 20% or more faster than my Celeron 400s. Could the 128K L2 cache of the Celeron chips (vs. the 512K L2 cache of the PIIs) be the culprit? I think so. Yves Gallot mentioned something similar on the Primes-L list a while ago. This brings us to an interesting point. Should the primenet server start default assigning celeron's 384K FFT mersennes, and save the larger ones for PII's/PIII's? -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: complaint
One version of Linux has paid the bill and passed the test, so at least one version of Linux is Unix. If you wanted to be picky, you could always say that a version of _GNU_/Linux has passed the test... The tests aren't for the kernel only, are they? But "GNU" stands for "GNU's Not Unix!", so how can it be Unix if it isn't? Wow! Could this be used for some kind of proof of the logical inconsistancy of the GNU system? What if M$ has been right all along? Scary, mind-blowing stuff. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Mailing list archive
By the end of next week I will remove the mailing list archive search function. The index for the archive occupies 1/3 of my disk quota. Considering how little it has been used, I can make better use of this disk space. I hope someone else would be willing to rebuild the index and host it. The mailing list messages up to Feb. 98 can be found below (about 4.2Mb). Why not host it on xoom.com or something? They offer free unlimited space. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factors of DecMega
Scott/all, I downloaded the newest beta for Prime95V19, and set it to ask for 10,000,000 digit Mersennes. In my worktodo.ini file, I got the line: Test=33219379,32 This surprised me! I had tested this number to 2^47, and Alex Kruppa had tested it to at least 2^55 (further investigation revealed 2^60). You should update primenet's files pertaining to this off of those at http://www.informatik.tu-muenchen.de/~kruppa/M33M/index.html -Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Macintosh Speeds
Now my question to the list is, would I be better off having these machines participate in GIMPS via MacGIMPS on MacOS or should I run mprime on Linux? My main concern is performance. Which performs better on the same hardware, MacGIMPS or mprime? I would guesstimate that they all have ~32 MB of RAM, and those that do not can get upgraded to 32 MB easily. Which route should I take? Umm, unless Mac's have changed a lot (ie become intel-based machines), you can't run Mprime under linux. Mprime is written in intel assembler! -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Simple question about P-1 factoring method
If I understand P-1 factoring correctly, then using it to a stage one bound of k to try to factor M(p) will find all possible factors less than or equal to 2*k*p + 1. Yes, of the form n*p+1 (not 2*n*p+1 :). This is for the simple reason that every power of a prime =k must divide Q (due to your definition of how Q is produced). Then by the fundemental theorem of arithmetic, (all numbers are able to be evenly divided into primes themselves), we know that any number k must be a product of powers of primes k, and hence divide Q. This is (unfortunatly) not useful for you, if your goal is to deterministically find factors less than a certain limit. P-1 would be much slower than trial division if that is your goal. P-1 is useful for finding very large factors that would be missed by trial division. Oop, just got your other letter: I've heard that P-1 is "more efficient" than trial factoring; does the proof go along these lines? Or is it more complicated than this? It's only "sort of" more efficient than trial factoring. It will find (some) large factors more quickly than trial factoring will, but it wouldn't find the factor 2^40*p+1, which (unless p is very small) would be found very easily by trial factoring. Of course; I realize that. I was only looking at it this odd way because of the trial factoring gaps I need to close. Since I already have the P-1 data, it's easy to do this. If I didn't already have the P-1 data, it would (most likely) be faster to simply do the trial factoring. Why would you have trial factoring with such low bounds, but P-1 with such high bounds? Just asking... -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: RE: Factoring more
Numbers above are factored to - --- 71002^72 57022^71 44152^70 35102^69 28132^68 21592^67 17852^66 13382^65 825 2^64 Isn't this the "optimal" configuration if all computers in GIMPS were identical? There are a number of 486's that are doing only factoring, does it take these into account? Think about it, there are a number of computers which should be factoring numbers faster than LL tests can be performed. Call this "factoring profit." Wouldn't it make sense to keep factoring profit as low as possible, as this could speed up the more immediate consern of sooner-to-be-performed LL tests? As an example, I just recieved the factoring assignment of 10258511, but I should think that we wouldn't even start these tests for some time. Why not go back and factor some 8M exponents further so as to save a few current LL tests? Wouldn't this actually get us to the next prime quicker? Or do I need to get more sleep :)? -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 second stage
I've just finished trying to factor F24 using the P-1 method with a bound #1 of 1,000,000. No factor was found. Unfortunately, I do not have enough memory to run stage 2. So, is there a volunteer that would be willing to run stage 2 on their computer. It will take about 3 weeks. You need 256MB of memory. The program will use 100 MB of that for the full 3 weeks. How does the stage 2 of P-1 work? Why does it require more memory? How do you know how long it will take if you don't even know what speed of computer is being used? :) The only references that I've seen to it say that it involves random walks and the birthday paradox. Can anyone point me to any online resources? (Library is closed for a week in preparations for the start of a new semester) Thank you, Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: More basic questions
2. Is overclocking of my Celeron 333 a good idea? I probably can't do it just now (EPoX P2-112A motherboard isn't made for such purposes), but I could upgrade it in about 2-3 months' time. No. This can often lead to errors, and newer CPU's are on the edge of sanity when it comes to heat anyway. I've heard that a Celeron can burn it self out completely in a few minutes without a heat sink. 3. How are the expected completion date and the chance that "my" exponent is a prime computed? The chance that your number is prime is computed using a conjecture of Wagstaff which states that: * The number of Mersenne primes less than or equal to x is about (e^gamma/log 2) * log log x. (Here gamma is Euler's constant). * The expected number of Mersenne primes 2^p-1 with p between x and 2x is about e^gamma. * The probability that 2^p-1 is prime is about (e^gamma log ap )/(p log 2) where a=2 if p=3 (mod 4) and a=6 if p=1 (mod 4). gamma is Euler's constant, ~.577, it is computed as (sum from 1 to n of 1/v)-ln(n)) 4. How come there are 8180017 iterations for M8180017? Shouldn't there be (p - 2) iterations for Mp (since we know L(1) and don't need to know L(p))? Or am I missing somethig? Or do I just cavil at it, and it is useful to know which Mp am I checking for a first glance at Prime95 output (most probably)? L(n) is defined as (2+sqrt(3))^n+(2-sqrt(3))^n. S(n)=L(2^n), hence L(1)=S(0)=4. Just because we know what L(1) is doesn't mean it should be discounted, it is still included in the count. We are trying to find if S(p-1) mod Mp=0, if S(0)=4 then there are p iterations. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: new accounts
The last time I did timings like this - admittedly, probably over a year ago, but the mers package hasn't changed much since, especially in terms of performance - this is wrong. SPARC LL testing - especially with MacLucasUNIX - is much closer to matching Prime95 LL testing than SPARC trial factoring - with mersfacgmp, say - is to matching Prime95's trial factoring, by, as I recall, a factor of about 12. Though I don't have specific timings, I imagine this would be the case. I was referring to the Mfactor program by Peter Montgomery. I have heard this performs considerably better than a GMP based program (written by Alex Kruppa) on RISC architectures. I suppose that I could/should check up on this with my SPARC-owning friend. The UltraSPARC would probably significantly outperform a similar megahertz PC, if we had similarly optimized code running on each. Perhaps. Again, I have no timings for this, but I would think that if you tried MacLucasUNIX on both a SPARC, and a PC, the SPARC would be the overall winner because of the massive amount of I/O that runs on LL tests. In factoring, I would imagine that the difference would be smaller, (using the same program). -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Multiple residues - enhancing double-checking
If B's checkpoint info doesn't match A's, the exponent is issued to another system C which calculates to the first checkpoint check in, as before. If we now have two matching residuals, the two systems supplying them are told to continue and the system with the "wrong" result is told to abandon that exponent. If all three differ, issue the exponent to system D ... The main way to speed this up is to have system C continue from the last residue that it is known that system A and B agree upon. Or, possibly even better (though more error prone) would be to have A and B recalculate from last agreed upon residue, and see if they now agree. This would waste at most 2 P90 months, without having to transfer it over the network, or have system D doing half the agreed upon work. I think it's safe to say that if system A and B can agree on the residue at that point, then it is the correct residue. As well as minimising wasted work, this scheme results in very little extra server traffic, since the systems all need to check in occasionally anyway. If Prime95 is altered so that it always works on the _smallest_ exponent it has "in hand", work should be completed reasonably quickly and in reasonable order. (Especially bearing in mind that this scheme completes double-checking at the same time as first tests!) Won't this mean systems constantly getting interupted in the middle of an exponent segment? Or would the systems only continue on one segment when they finish the current one? When a prime is found, the discovery credit ( any prize money) should obviously be split between the two users who ran the last iteration on the exponent in question. This makes sense, though it might not be needed. This scheme would work best on people willing to stay with GIMPS for the decade required to finish the range. Many of these people have (fast) networks with lots of computers on them. The check/double check computers might be right next to each other, owned, and run by the same person. This will not matter for some time. Does anyone have current data for % mistakes? -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Multiple residues - enhancing double-checking
This idea is rather obvious, and no, I don't remember seeing it either. This had been discussed earlier. Brian and I talked about it for a little while, he came up with the original idea. I think the idea has definite merit. If an error does occur, it's equally likely to happen at any step along the way, statistically. Errors are every bit as likely to happen on the very first iteration as they are during the 50% mark, or the 32.6% mark, or on the very last iteration. True, but if the system is malfunctioning then the errors should start early. Especially as the exponents get larger and larger, I see a *definite* possibility to reduce double check times by having first time LL tests report residues at certain "percentages" along the way. Yeah. The error rate should be proportional to the runtime which is increases with the square of the exponent (ouch!). Just for example, every 10% along the way, it'll send it's current residue to the Primenet server. I'm guessing that you mean a certain amount of the residue. Sending in 10 2meg files for *each* exponent in the 20,000,000 range would get very unwieldy, and inconvenient for people and primenet. Of course, this would only help if we were running more one test for the same exponent at the same time (otherwise, this would just be a pointless way to do a triple check). They would either have to be coordinated (running at the same time, logistical knightmare), or (as Brian suggested) have a "pool" of exponents running on one computer. That is to say when one computer finishes to X%, it reports its 64-bit residue to primenet, and waits for the second computer working on the same LL test to do the same. Until the other (slower) computer reports in, the (faster) computer works on another exponent. This would speed up the entire project, but it would slow down the individual exponent, which would make people mad :(. I forget the numbers being tossed around, but you'd only save 50% of (the error rate) of the checking time. As I pointed out above, the error rate should increase with the square of the exponent (plus change). This means that if 1% have errors at 7mil, 22% will have errors at 30mil. -Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Multiple residues - enhancing double-checking
That is to say when one computer finishes to X%, it reports its 64-bit residue to primenet, and waits for the second computer working on the same LL test to do the same. Until the other (slower) computer reports in, the (faster) computer works on another exponent. Not at all. The first-time check goes its way, but reporting partial residues to coordinator / primenet from time to time. Later, often when first LLTest was finished long time ago, somebody receives: Double-Check: M23780981,64,863FF87,678676AA,FF637BC,[...],CRC:9923FDA. This scheme makes almost no sense for normal double checking. This is becuase it would save *no* time at all. Think about it, even if you identify that an error ocurred in the second week of a 3-month test, you still have to run it to completion, and a third test must also be run. (So 3 LL tests must still be run if an error ocurrs). This schema makes possible simultaneous checking, though. But the start-stop mechanism you describe has little sense. The method that you describe would only allow simultanious checking if the computers were of equal speed, or if one kept working on the same exponent, and the other computer kept getting further behind. The scheme that I described (and Brian thought up) would allow the computers to run at the same exponent/time, while still keeping busy. Sorry about my bad english, and it's even my first language! -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: massive GIMPS cabinet
Having one power supply per computer, besides the convenience of having it self contained, is the fact that the fan in a power supply is used not only to cool the supply itself, but to circulate air throughout the entire case. This is especially true for ATX spec cases and supplies, but is a general rule of thumb for all systems. The main problem with running one supply/system is that I simply don't have that many supplies. These are mostly old ALR computers (486/66's) which I was able to save from the dumpster at the used computer store that I work at. We took the standard AT power supplies out of them, and sold them as used supplies. It certainly would not have been good for my job if I had said "Hey can I have these twenty $10 items, I thought you wouldn't mind." Images of the sarcastic comic book shop owner on the Simpsons "Please take my money *I don't want it*." Motherboard connectors are plentiful as people often bring in bad PS's, and I have been cutting off the connectors as of late. Though of course this involves bulk soldering :(, but that was the "fair amount of work" I mentioned. You mention having central cooling for a cabinet, but I wonder if the added power that a central cooling unit (a 120V cabinet fan?) is offsetting any potential power savings by running less supplies total. Same problem as above, but when you add up the cost (in watts) of 20-30 12V fans, the gains become a bit more apparent (though still possibly not worth it). Even though most power supplies come in ratings of at least 220W or so, the average motherboard uses only a fraction. More power savings can be had by finding less watt hungry hard drives. Laptop drives are 2.5" and generally consume far less power than your average 3.5" drive. There are adapters aplenty from electronics shops that let you plug your 2.5" drive into a normal IDE cable. CD ROM drives and floppies are big power hogs too, but they're not on all the time anyway, so that's not a problem. They will have only a floppy attached, which will run once (at boot up). As long as you have fun, why not? :-) Of course, then if you have one supply go out, you lose all your computers. But there's always a tradeoff between cost and reliability. The servers I work with (even the storage units) all have N+1 power supplies...but the cost! Whew! This shouldn't actually be a problem as the computers will only be running factoring assignments, and they should get these only a few at a time. The assignment server will be running on a UPS, and will keep track of which exponents are assigned. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: massive GIMPS cabinet
They will have only a floppy attached, which will run once (at boot up). Are these basically just "NC's", with a boot floppy and a network Windows 95 location? You lousy Microsoft freaks! They will be linux boot disks that will run either Mprime v19, or Brian's factor95.c. We haven't decided whether to use Token Ring (has the advantage of being free), or ethernet (has the advantage of good development under Linux). The assignment server will probably be something very simple, maybe just using rlogin and perl. But the thing isn't built yet, so this is just a pipe dream. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Pepin's Test, etc.
If Pepin's primality test was run on F24, we could determine if F24 was composite or prime. The chances that F24 is a psuedo-prime (a composite pretending to be a prime) are very slim so it is worth the time to run the test. I estimate the time required would be 6-9 months and we could do it with existing software. Pepin's test on Fermat numbers is deterministic. There is no such thing as a Pepin psuedo-prime Fermat number. -Lucas P.S. Shouldn't this discussion be on Primes-L? _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Cut the Crap!
Can we cut the crap on this list? Hear, Hear! Especially the neo-poaching thread. This is simply too volatile and pointless a thread to waste our time on. Quite frankly, I'm also getting kind of annoyed with "When do you think we will see a [power of ten] digit prime?" type questions also, though some of the subtreads have been interesting. Better yet, can we have another mailing list that is just announcements? Interesting idea, and one that makes sense for those who have less time on their hands. It seems almost like the FAQ has reduced math on the list and increased pointless "prediction" questions. Though of course I am probably just confusing correlation with causation. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
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
Re: Mersenne: Size of Mersenne Primes - 3 Questions
OK - I'm not a math guru, and am new to the list. I can't find a recent archive so I hope this isn't a repeated question. Perhaps there is someone out there that could help me get some answers to the following basic questions ideas. Feel free to send me email directly. Thanks! Check the FAQ, mentioned at the bottom of every message, www.tasam.com/~lrwiman/FAQ-mers 2) What are the approximate N's that correspond to the beginnings of these areas? See the FAQ, Q5.3. 3) Assuming the continued (exponential?) growth of GIMPS, when will GIMPS begin to assign work in each of these areas? I think it is parabolic. I seem to recall that someone said we should reach 20.5 million by spring 2005. I don't know when we are projected to reach the deca-mega-digit range. I think the stats are available at http://entropia.com/ips/ though I'm not sure. I suspect that the ranges for N that GIMPS is searching are far from the next eligible EFF prize for 10 million digit primes. I was wondering if anyone knows what the smallest N is that gives a 10 million digit prime might be. (I have no way to calculate it myself.) We are searching far from that range. I imagine that a number of people would begin testing in that range after V19 becomes available. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Mp and E-Cash
Unless George/Scott set some legal mumbo jumbo that ties into use of the program/source/services, they're simply not "entitled" to any prize money. I'm forced to agree with Aaron, aparently at gunpoint :-) (and I said this a while ago, BTW). Even if they (George and Scott) did this, then there would still be MacLucasUNIX, or everything else in the mers package, as well as Ernst's program, and good ol' lucas.c. Any of these could be used. We've really got to put our feet back on the ground here. If we did put a license change on all of George's program derivitives, we would still have to get Will and Ernst to change their copyrights, and Richard Crandall. In fact, is the DWT patented? If so, Richard Crandall could claim the $100,000 for himself since I think that the programs that have a prayer of finding the Deca-mega prime would use his algorithm. If someone read on George's page "running this software means that you lose most of the prize money." They could do one of 3 things: (1) Say "Oky-doky" and download/run George's program (2) Say "Well, (sensored) you" and continue surfing (3) Say "Where can I get another program?" and find the others I would imagine that the way they dole out the prize money is because use of their software implies agreement with certain terms, i.e. that you agree with the prize money disbursement outline. I didn't find anything specific, but then I didn't try and join them. I either missed it, they just "fudged" over it and hope that no one notices, or the RSA announcment covers this somehow. And again, the first deca-mega-digit prime may not be a Mersenne anyway...who can say? :-) Yah, it could be proth, or something. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Evil, evil prize thread
At present we find approx. 1% of the LL test results submitted are incorrect. That figure seems a tad high. After double-checking, there would be a 0.01% chance that BOTH tests had failed, which seems very high to me. 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. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Hardware FAQs
All, On the subject of a hardware type FAQ/section in FAQ, here are the few FAQs that I could think of off the top of my head. I'm guessing others can think of more. I'm really not qualified at all to write about win95/nt/os2 questions. I've never used os2/nt, and I haven't used win95 in over 3 months. I haven't had it on one of my computers in over 6 months. I never ran any Mersenne related software on any of these platforms. Etc... Q: Does Prime95 decrease battery life on a laptop? Q: What is a Roundoff error? Is my computer broken? Q: Why does my computer start making noises when I run Mprime/prime95/NTprime? These I can answer pretty well. For other suggested questions, I should probably be able to get the answers out of the archives. -Lucas P.S. Are archives available past February 1998? _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Worth it?
Sorry if this is sending out twice, I wasn't sure that it got sent the first time... As I understand the Pollard P-1 algorithm, the time required for 1 bit of the exponent would be equal to 1 iteration of the LL test (one squaring mod Mp), so values wouldn't be that hard to create. (timing values, for comparison with regular factoring) The main problem is that to get a bound of any reasonable size, and try multiple bases, you are looking at a time comperable to the LL test. (I suppose that on further investigation, with a bound value for factors of the exponent at 10,000 we are looking at about 14,000 squarings mod Mp, which is really not all that many) Also, one of the keen things about GIMPS is that in its search for primes, it came up with loads of factoring data for Mersennes. However, the P-1 algorithm would make any factor distribution data a lot less usable (as it would not include P with P-1 having a large prime factor). (That is to say, if the P-1 algorithm was used, it still couldn't find all the factors 2^64, unless we are talking about incredibly high bound values) On the other hand, the P-1 algorithm can take advantage of the special form of Mersenne factors. We know that P-1 must be divisable by the Mersenne exponent, and that in 1/2 of the cases, it is divisable by 8. (we know that the factors must be of the form 2*k*p+1, hence the factor-1 must be divisable by 2*p, or in the form 8*n+/-1, hence the factor-1 must be divisable by 2 or 8) I'm not sure that I understand what you are saying, but the following are a few observations that I made when I looked at the problem a few years ago. The major stumbling block for an efficient P-1 is the implementation of a time and memory efficient GCD. If one has a good GCD algorithm then a stage 1 only implementation becomes cost effective for exponents around 3 million. However, the cost savings is tiny, probably less than a percent overall. The major benifit is that one does not need to double check the exponent. Yup, silly me. You are quite correct, of course, that the GCD is the most time consuming part. I imagine that from what you are saying, it gets more cost-effective the higher the exponent. How does it look at around 33219281? -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: FAQ registered with search engines
I added the FAQ to the following search engines: Lycos Excite Yahoo Altavista AOL netfind Webcrawler HotBot InfoSeek -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Meetings (was $100,000...)
Have a party... wouldn't YOU like to meet the other people working with GIMPS? Frankly, this wouldn't be THAT expensive, and we could even make it a symposium or something call for papers or research in the area of computational number theory. I like the idea of a symposium, I'll bet that colleges would be willing to host it. In Illinios, we could host it at UIUC (Urbana), ISU (Normal), or U of C (Chicago). Maybe we should set a number of these up. I would personally like to meet the GIMPSers in the midwest. I guess the biggest problem would be coming up with the papers. I don't mean to offend anyone, but I doubt that many of us are involved enough (or know enough) to write papers, and such. I suppose those of us with more interesting computational setups could tell about them, or something. Those of you with ideas for an Illinios/midwest meeting, write me privately. Or we could have monthly meetings in coffee shops like 2600 does... That'd be keen. -Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: The $100,000 award for 10,000,000 digit prime
I hate the charity idea only because it seems to me that a "Mersenne Scholarship Fund" would do much more for our project in many ways: 1. We could control where the money goes to a greater extent. 2. It would allow us to contribute a great deal more mathematics in general. 3. More notariety. I doubt that we could actually get many scholarships out of the $100,000. Maybe scholarships for 6 or 7 people, any more and we start sending them to community colleges. (though, if you want to send someone to college, I wouldn't mind it ;) I like the idea of using some of it to get George some computers, and maybe pay his electric bill for a year :) Ok, that's maybe 10K at the outside, then we run the risk of just cluttering his house with computers. I also like the idea of giving some of it to Scott. And though I think that Colin Percival is right when he says that Scott gets most of the reward from the publicity, he would get this anyway. Especially if newpaper articles read $15,000 was given to Scott Kurkowski, who gives his server time to run the primenet software... Different message, same author: 10% for George 10% for Scott 10% for Discoverer 10% Charity/Scholarship (The Mersenne Scholarship Fund) 60% divided evenly to everyone who contributed, based on CPU cycles contributed after the last Mersenne prime found. ~6,000 people in gimps. $60,000/6,000=$10 on average. Hardly worth doing... Though personally, I'm not to comfortable with the idea of splitting the money away from the winner. I doubt that the winner would actually do anything to deserve the money, but I also think that many, many people would be discouraged to read "if you are the lucky discoverer, you don't get to keep 90 grand that the EFF would give to you were it not for the software you are about to download." This would also entail a restrictive license agreement, which some lawyer would write, and we all know that a "volunteer project's" credibility goes straight down the tubes when lawyers get involved. Hey, if you don't believe it, try reading your bank statment, and your credit card bill's fine print. Then tell me how much respect we would lose in the name of legality. I think the only reasonable way to get any money out of the hands of the finder would be to ask them to give some of it away. I should think that there would be many people who would be willing to do this, but I don't think it would make us look good to write and ask to give it away. -Lucas Wiman _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: General release of the FAQ
I think the FAQ is ready for "general" release. I have been working on it for 20 days, and it includes most of the FAQ's and some of the not-so-FAQ's. I have tried to make it as understandable as possible, though I am not a very good writer. Please send me any errors in it (technical, spelling, and gramatical). There were of course many contributers to it other than me, those were: Peter Montgomery Chris Nash Jud McCraine Chris Caldwell Brian Beesley Ken Kriesel Pierre Abbat Jay Hill Vincent Mooney Jr. I would like to thank them all. At many points, I directly quoted these people, so if any of you have problems with that, tell me. I will register the FAQ with the major search engines in the next few days. I really hope this FAQ reduces repetition on the mailing list. thank you all, Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
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
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
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
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
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
Re: Mersenne: re: Mersenne prime exponent binary
I'm not sure what the law of leading digits is, but I read this as talking only about base 10 numbers... so the leading digit 1 is compared to leading digit 2, 3, 4, ..., 9. Right? So for numbers 2^n (in Base 10), [or is it 2^p?] there are a lot more leading ones than one would "expect" naievely (you would expect 1/9 to start with "1", I imagine). As Jud said, this is called Benford's law. It was originally discoved in the late 1800's by "Some Guy," who was never noticed. It was then rediscovered by Benford in the 1930's. I think that he worked for ATT. Both guys discovered this law by looking at wear-and-tear on Logarithm books. This law states that for a given base a, and a given leading digit b (0ba-1), the probability that the leading digit is b is log_a(1+1/b). What Peter was doing when he was talking about the second digit was (aparently) converting it to base 4, and working witht the usual Benfords law. The law of leading digits predicts that, for decimal numbers, log10(2) ~= 30.1% will have leading digit 1. Uh, won't they *ALL* have a leading digit of one? Anything with a leading digit of ZERO can be totally discounted Read the rest of his email, and you will be enlightened... The law of leading digits predicts that, for decimal numbers, log10(2) ~= 30.1% will have leading digit 1. It depends on what set of numbers you are considering. That's the point of Benford's law, it is supposed to be relatively independent of the set of numbers. Note that in the set of mersenne prime exponents (so far), the leading digit 1 (in decimal), turns up 10 times as opposed to the 4.2 times expected by equal leading digit distribution... -Lucas Wiman P.S. I seem to recall this being mentioned (benford's law), shortly after I joine the list. May have to go into the FAQ. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Why can't we...
Take 2 Mersenne numbers, m1 and m2 (m1 m2). Do the usual LL series, but use as the modulus m1*m2. At the appropriate step, check if the remainder is divisible by m1. If so, then m1 is prime. At the end, check if the remainder is divisible by m2. If so, then m2 is prime. This allows us to do two (or more) tests for the price of one. What is the obvious reason we don't do this? This would require more than double time. Think about it like this: Take two mersenne numbers 2^p-1, and 2^n-1 with p~=n (For the purpose of clarity we will assume they are close enough to be considered equal) Now, an LL test requires O(p*(p*log(p))) time. (~p multiplications of O(p*log(p)) time) Hence the time required to perform them on p and n is O(2*p^2*log(p)). But, the test you suggest would be require O(p*((2*p)*log(2*p)))=O(2*p^2*(log(p)+log(2))) Thus, your suggestion adds on O(2*p^2*log(2)) time. Hope that helps, -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Head's algorithm for multiplying mod n
All, In the book _Primes and Programming_ Head's method of multiplying two numbers mod n is mentioned. Is this actually more effiecient than simply multiplying the two numbers and taking the modulus? If so, is it implemented in the various mersenne factoring programs in use? Thankyou, Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Publicity from the 38th
all, I think that we should put the publicity from the 38th mersenne prime to good use. If we all write letters to the local paper, then we can probably gain a very large number of people. Stick encouragements to join on your website, in you .sig files, anywhere you can think of. Be sure to mention the prize money involved in the finding of the 38th. This should speed us on our way to victory... -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Publicity from the 38th
Actually I think mentioning the prize money might constitute deception, since the next prize isn't in reach, yet. However, I agree with your sentiment, except - _what_ "victory"? It might be interpreted as a deception, I suppose... "victory" would of course be finding another prime... -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Head's algorithm for multiplying mod n
Pierre Abbat writes: In the book _Primes and Programming_ Head's method of multiplying two numbers mod n is mentioned. Is this actually more efficient than simply multiplying the two numbers and taking the modulus? Look at it this way. Head's method is essentially binary long multiplication, with the "wrinkle" that you take the remainder modulo n after each shift add operation. That is going to be a *lot* slower than FFT convolution, for numbers the size of the Mersenne numbers we're testing! FFT is O(n*log(n)) where n is the number of limbs in the numbers being multiplied. Head's method is O(n^2), with O being slightly smaller than for straight long multiplication. A recursive method splitting the number in the middle, then doing a subtraction trick to make three instead of four submultiplies, is O(n^y), where y is log(3)/log(2), which is about 19/12. Well, I wasn't talking about the massive scale of numbers used in LL tests. I was speaking of the 95 bit integers used in factoring, and using Head's algorithm in the calculation of 2^p mod f. I doubt that FFT would be worthwhile here, and would probably slow it down considerably. Chris Nash writes: But enough already. One thing I'm surprised nobody has mentioned yet - is it even in Lucas' FAQ? - is that modular reduction in the Mersenne case is sinfully inexpensive. Even with a pure integer, no FFT implementation, reduction mod 2^p-1 is very quick - take the lower p bits, take the rest of the number shifted down by p bits, add them together. The size of the original number is usually around 2p bits, so one iteration of the shift-and-add will get the result correct to within 1 extra subtraction at most. I think I might split off the parts about modular arithmetic into their own section, or in the beginning stuff section. I'll probably add this question sometime tomorrow. -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: question
Now lets only focus on the set 2^p - 1 with p prime, i.e., the set of numbers that we are checking out at GIMPS. Has anyone proven that an infinite number these are NOT prime (this is VERY likely to be true)? It's nice to be able to say this, but it is in the FAQ. Check it out at http://www.tasam.com/~lrwiman/FAQ-mers The last three questions (those in section 4) are pertinate to these questions. I would ask that before anyone sends a question to the list, please check the FAQ if it deals with basic questions involving the following: (1) Basics of a mersenne number (what is it, how many digits, etc...) (2) The Lucas-Lehmer test (repeating LL remainders, modular arithmetic, etc...) (3) Factoring Mersenne numbers (how is it done, how do we sieve, etc... (4) Distribution of Mersenne primes and numbers (how many mersenne primes, and how factors and mersenne primes are distributed) If you still have questions after reading the relevant sections of the FAQ, by all means send them to the list!! Thank you, Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: question
If 2p+1 is prime then it divides 2^p-1. If it has been proven that there are in infinite number of prime pairs p and 2p+1 then this proves that there are an infinite number of 2^p-1 that is not prime when p is prime. These are called Sophie Germain primes, and it has been proven that there are an infinite number of them, therefore there are an infinite number of composites of the form 2^p-1 when p is prime. This is not quite right. The primes must be ==3 mod 4. For example, 29 is prime and ==1 mod 4, but 59 does not divide 2^29-1. I'm not sure whether or not it has been proven whether or not there are an infinity of Sophie Germain primes of the form 4*n+3. I imagine there would be, as there are an infinity of primes in the form 4*n+1 and 4*n+3. -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: More on the FAQ
Chris, on your website http://www.utm.edu/research/primes/notes/faq/NextMersenne.html, you say: "This means that the geometric mean of two successive mersenne exponents is 2 raised to 1/e^gamma or about 1.47576." The definition of geometric mean of two numbers a and b is: sqrt(a*b) Therefore the geometric mean must be between a and b. I think that you mean that the geometric mean of two successive mersenne numbers is 2 raised to the (1/e^gamma) raised to the index of the mersenne numbers. -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: M38
The page belongs to a previous record holder... Took me about 30 seconds to find it. It's nice to see a thirty-eighth line in /root/math/ref/mers... -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: M38
The page belongs to a previous record holder... Took me about 30 seconds to find it. It's nice to see a thirty-eighth line in /root/math/ref/mers... I didn't! Am I _that_ bad at searching the web? I looked at Gordon's page and Roland's page (found nothing), but couldn't find Joel's page. You aren't searching for the right people. He didn't say it was a *GIMPS* record holder. You've just gotta know where to look. Help! :-) All right, here's a hint: he held the record for largest prime, which was also a non-mersenne prime. Check the largest prime by year... -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: M38
Found it -- 2^6972593-1 :-) Well, finding that in 30 seconds must mean you knew it was there, or you were incredibly lucky... Does George know about this? Lucky. I went to yahoo.com and typed in 38th, and then stopped. I realized that I should look for the record holders, and through some obnoxious bit of trivia that my brain doesn't let go of I happened to have his URL memorized. Well either that or I am *SEARCHER SUPREME*, but then I would have been the first to find it, on Landon's site. I would assume that George would know since he probably gave the exponent to him in the first place. -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: distribution of factors (was 10,000,000 digit prime)
NO! The _correct_ formula is ceil((10^7-1)/log_10(2)) = 33219278. Aww, mine was pretty close ;-) The point is that 2^n have 1 decimal digit for n 4 ;-) As it happens, 33219278, 33219279 33219280 are all composite and therefore are not contenders for generating a Mersenne prime. 33219281 _is_ prime, the status of 2^33219281 is (so far as I know) not known at this time ... unless someone found a factor bigger than my 2^40 search limit. Well, I don't think that 2^33219281 is prime (factors 1, and 2) :-). But 2^33219281-1 has no factor less than 2^52. No I am not searching in this range, but I made a made this a special case. I am currently searching between 2^47, and 2^50. Which should take almost two more months (unless I find a load of factors, that should make things go faster :) In that range, I an finding about 5.5% to have factors. If this holds, that would be about 3970 new factors, added on to all the other factors that I've found, that makes 19868 factors, less than half of those less than 2^40, despite the fact that the range I tested is 1023 times larger. I realize this is probably a FAQ, (and I intend to put it there), why is the distribution of factors so non-linear? -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Mersenne FAQ 1.1
All, Here is version 1.1 of the FAQ. I corrected a few typos. I then added 500 more of them when I added the LL section. The LL section needs major revision, and clarification, especially the repeating LL part. I think we might add a section on FFT, and DWT, though I don't know enough about math to do it. I also like the idea of a history section. I have read something about the history of GIMPS, as well as some of the list's archives, but I have only been here since February... -Lucas Wiman Q: What are mersenne numbers? A: Mersenne numbers are numbers of the form 2^p-1, (2 to the pth power minus 1) Generally, when mersenne numbers are mentioned, mersenne numbers with prime exponents are what is actually meant. Q: What is a mersenne prime? A: A mersenne prime is a mersenne number Mp which is prime. P must itself be prime, otherwise Mp has a trivial factorization. Q: How can we prove these massive numbers are prime? A: We can use a method known as the Lucas-Lehmer (LL) test. It works like this: For p odd, the Mersenne number 2^p-1 is prime if and only if 2^p-1 divides S(p-1) where S(n+1) = S(n)^2-2, and S(1)=4 Q: Won't those S(n) get huge very quickly? How can we check whether 2^p-1 divides S(p-1)? A: Yes, and with the magic of modular arithmetic. Modular arithmetic deals with remainders from long division (like you did in grade school). We say that if a==b mod c if a and b both have the same remainder when divided by c (which is read "a is congruent to b mod c," on paper, we would write this a=b mod c where = has 3 horizontal lines.) Another way to think of this is (a-b)/c is an integer. Here are the most important things involving modular arithmetic: (1) if a==0 mod c then a is divisable by c (2) (a+b) mod c = (a mod c)+(b mod c) mod c (3) (a*b) mod c = (a mod c)*(b mod c) mod c (4) a^b mod c = (a mod c)^b mod c Now, we can define a new series (call it s(n)) where s(1)=4, and s(n+1)=s(n)^2-2 mod (2^p-1). Using these rules of modular arithmetic, we can see that 2^p-1 divides S(p-1) if and only if s(p-1)=0. Therefore, the numbers we work with can never get above (2^p-1)^2 (no bigger than 2^p-1 with some cleverness). Q: If the remainders of the LL series ever repeated, we could skip the rest of the test, because it could never equal 0. Why don't we test for this? A: Well, a simple heuristic argument involves simple probabilities. Think about this, for the recurrance to be important, it must occurr in the first p-1 iterations. *BUT* there are 2^p-1 possible remainders, that means that the that the probability of such a recurance is aproximatly (p-1)/(2^p-1). These odds are better than suddenly being transported to Mars by quantum fluctuations, but worse than winning all the lotteries in the world simultaniously. (well, of course depending upon the size of p, when it gets large enough, the probability can get arbitrarily close to zero) Here's another way to think of it: as the S-sequence is defined above, S(n)=L(2^n) (where L(n)=(2+sqrt(3))^n+(2-sqrt(3))^n) Now suppose for instance the recurance occurred between L(2^(n-3)) and L(2^(n-2)) - which, even assuming the "first" recurrence is equally likely anywhere, would occur with probability 50%. The S-sequence would not even see it. And furthermore: We can illustrate working modulo M23 = 8388607 = 47 * 178481. 3 is a quadratic reside modulo 47 (e.g, 12^2 == 3 mod 47), so 2 + sqrt(3) is in the base field of order 47. The multiplicative order of 2 + sqrt(3) divides 47-1, and turns out to be 23. 3 is a quadratic nonresidue modulo q = 178481. The order of 2 + sqrt(3) divides q + 1 = 178482 = 2 * 3 * 151 * 197 and turns out to be 178482. The least common multiple of these orders is 2 * 3 * 23 * 151 * 197. So L(2 * 3 * 23 * 151 * 197) == L(0) mod M23. For the L sequence, we need two powers of 2 whose difference is divisible by 2 * 3 * 23 * 151 * 197. The orders of 2 modulo 3, 23, 151, 197 are 2, 11, 15, 196, respectively. The order of 2 modulo 3 * 23 * 151 * 197 is the least common multiple of these orders, namely 2^2 * 3 * 5 * 7^2 * 11 = 32340. To include a factor of 2, we need L(2^32341) == L(2^1) mod M23. That is, S(32341) == S(1) mod M23. This is far more than 23 LL steps before the sequence repeats. (Thankyou, Chris Nash, and Peter Lawrence Montgomery) Q: Wouldn't it make more sense to record the S (without taking the remainder) series, and save the result, thereby saving alot of work? A: No. The number of digits in the S series doubles with each iteration. thus by the 270th iteration, you've run out of protons in the universe to store it in. Q: If some s(n) is larger than half the size of the mersenne number, wouldn't it make sense to take 2^p-1-s(n) and square that and subtract 2? A: This would usually take off one bit. When there's seven million of them, it really doesn't make much difference, and it would take longer to determine if s(n) is greater than 2^(p-1) than th
Re: Mersenne: Re: 10,000,000 digit prime
The 10,000,000 digit prime would have an exponent of over 3010299.956, or 3010300 which is found by taking (log 2 * 10,000,000) Actually, it's log10(2) * 10,000,000, which is a different number. Of course, since I'm not at home, I can't figure out _that_ number offhand, but see the posts from some weeks back to get the exact first exponent. The formula for determining the number of digits in Mp is p*log_10(2). Therefore, to find the first one with 10^7 digits, we find ceil(10^7/log_10(2)) which is 33219281. Yes, this is going in the FAQ... -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Mersenne FAQ
All, Here is a potential FAQ of the mersenne mailing list. At the moment it only deals with factoring, but this should change. Any suggestions for what should be in the FAQ? Any mistakes? Any Clarifications? -Lucas Wiman Q: How is factoring done on mersenne numbers? A: We check a potential factor n of Mp by seeing if 2^p (mod n)=1 Q: But doesn't this mean using very large numbers, and computing 2^p? A: Not at all, there is a very simple algorithm for finding a^b (mod c), and here's how it works: we set res=1, then multiply res by a^(2^n) mod c whenever the nth binary digit of b is 1 a^(2^n) mod c is relativly easy to calculate through repeated sqaring of a mod c (note that for any o,p, and m, (o^p)==(o mod m)^p (mod m) where == is the "congruent to" symbol) Q: That's still a lot of factors!!! A: Well we can significantly reduce the number of factors through some simple theorems which state that: (1) any factor of 2^p-1 must be of the form 2*k*p+1 for k0 (2) any factor of 2^p-1 must be of the form 8*n+1 or 8*n-1 for n0 (3) the smallest factor (other than 1) of any number must be prime Theorem (1) reduces the number of cases to 1/(2*p) of all numbers. Theorem (2) reuduces those to 1/2 of those. Theorem (3) can reduce the factors down to only prime numbers, but that takes too much time. It is generally better simply to sieve out potential factors with very small factors. Q: But how can you sieve out small factors from potential factors? A: Well, I think an example would be most illistrative. Say we want to seive out all potential factors divisable by 3, 5, or 7. Well we can create an array of 3*5*7=105 elements, with all elements set to 1 (we'll call this array N). Then elementate all N[i] such that i is divisable by 3, 5, or 7. Then we can keep a running value of 2*k*p+1 mod 105 then if N[2*k*p+1 mod 105]=0 we skip that factor, and go on to the next one. Q: How much does all this actually help? A: The sieving for small factors (up to 17), as well as theorem (2) can can seive out about 32% of potential factors of the form (2*k*p+1). Q: Wouldn't it be more effiecient to check prime numbers and see if they divide as certain 2^p-1? A: Yes and no. It is theoretically more effiecient to do this, however this also produces uninteresting (and relativly useless) results for where p itself is composite. Q: A prime number cannot divide more than one mersenne number, so why not create a table of all the prime numbers which divide mersenne numbers so as not to duplicate work? A: This isn't really workable because it would take longer to check the table than it would to just check the factor. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Still more 10,000,000+ digit factors!!!!!!!
I have found 1868 new factors in the range of Brian's 10,000,000+ digits. All of the other primes in this range have been tested through 2^47. They are avalaible at: http://www.tasam.com/~lrwiman/fact47 or http://www.tasam.com/~lrwiman/fact47.gz -Lucas Wiman P.S. If these posts are getting annoying, at least they will be getting less frequent. P.P.S. Does anybody but Will care about these new factors? Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Still more 10,000,000+ digit factors!!!!!!!
P.P.S. Does anybody but Will care about these new factors? Heck yeah... keep 'em coming... a bit more discussion of how you're finding these things could be interesting, tho... Well, that is probably the least interesting part. I use Will's MersFacGMP program on a PII/233 running RedHat 5.2. Factoring to 2^47 is fairly easy, I suppose, but where are all these stragglers coming from? Well yes, especially when the numbers are as big as 33mil, but when there are 91423 remaining numbers, it takes a bit longer to calculate. (89555 after factoring to 2^47). Now I'm trying 2^50, (that should take a while). What do you mean by stragglers? -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
re: Mersenne: Factoring and Databases
Why test factor for primes in the range 2^1 to 2^10? If someone made the table I described, it is possible that all primes less than 2^10 are in the table I have described because they are known divisors of a Mersenne number OR are not candidates for dividing any Mersenne number by other conditions (subject to the ALERT above). Remember that the smallest factor of M_p (p prime) is 2*p+1. This is the smallest factor in a fair number of cases. This means, however, that the smallest M_p which has a factor around 2^10 must have p~=2^9. I think we're well past that point. If I understand you correctly, you suggest making a massive table of primes, and what M_p they divide. This would be very inefficient!! Since I doubt that you could Store such a table in memory, the lookup time would be enormous compared to the time spent to actually testing the factor. Even if you could store it in memory, I think that the lookup time would still be greater than the time spent testing the factor. If you mean to create a range (eg: 2^32) and test for which M_p divide primes in that range one by testing the potential factors, this might work, though Chris Nash did this on smaller ranges, and most of the results weren't worth much. I think it is much faster to test exponents for factors rather than the other way around, when dealing only with prime exponents. -Lucas Wiman Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Meganet Corp.
Did I write polynomial anywhere ? I said deterministic primality proving algorithm. I thought that perhaps you mispoke, since your statement seemed incorrect. My point was that trial division is deterministic, but you said there was only one such algorithm. -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Re: Meganet Corp.
"Polynomial?" I think and please correct if I am wrong that trial factorisation using long division requires O(sqrt(n)*log(n)) operations. sqrt(n)*log(n) is polynomial in n e.g. it is less than n^2. Presumably when measuring the order of factorisation algorithms you guys use n ~ e^x and then measure the order in terms of x? Well, it is polynomial to n, but we want it so that the runtime is polynomial to the digits of n (log(n)), which O(sqrt(n)*log(n)) is exponential to log(n). -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
