RE: Mersenne: The $100,000 award for 10,000,000 digit prime
On 19 Jul 99, at 18:40, Todd Sauke wrote: Alex, The group you seek always has 2^n elements. All bit combinations are possible. (P = 2^p-1 is "minus one" in n-bit words. 2*P is minus two, etc. up to 2^n*P which is 0. All bit patterns occur.) Todd Sauke In general, what you say is true - but try computing the LL sequence to one hexit precision (i.e. working to base 16). Starting from 4, we get 0x0E, then 2 ; since 2*2-2 = 2, _all_ the subsequent values are 2, so we can compute the low order 4 bits of the umpteen zillionth term of the LL sequence as fast as we can load the value 2 into a register! Oops - doesn't work - forgot to take the modulus - otherwise there could be _no_ Mersenne primes except 7 = 2^3-1 ;-) It's taking the modulus which is the key to the whole LL test, and what the problem essentially boils down to is _any_ way of computing the remainder of a division whilst working to a lower precision than the number of bits in the divisor. Now I wouldn't say that this is completely impossible, but the very idea seems about as counter-intuitive as the notion of having several networked processors cooperating on an FFT without being able to share data at memory bus speed and without being significantly delayed by waiting for each other's intermediate results to become available. Regards Brian Beesley _ 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
On 19 Jul 99, at 3:57, [EMAIL PROTECTED] wrote: *) Somebody finds how to parallelize the FFT using little communication. The wall-clock time might be reduced 10-fold, but the CPU time increased 16-fold. This could be great for verifying a new Mersenne prime, but does it qualify for the money? Surely that's been done - long since - for application on massively parallel processors (vector machines). *) Somebody finds a novel way to choose elliptic curves modulo Mp, using the information that its prime factors are == 1 (mod p) and that 2, -p are quadratic residues modulo any factor of Mp. This lets the trial division phase search 10 bits higher, such as searching to 2^74 rather than 2^64. Does its finder get any money? I think this would speed us up only a few percent at best. Nevertheless it's a novel approach could have other useful ramifications. I mentioned to George that I think the best way to decide which improvements are eligible for any share of an award would be to have a vote with the electorate consisting of previous Mersenne prime discoverers. *) Somebody finds a way to verify the output of the LL test without a complete rerun (cf. verification of digital signatures). If this eliminates the need for double-checks, does it qualify? That sounds interesting! Of course, if we could find a _quick_ way of computing a few bits of the residual, we could use this as a filter which would remove a large proportion of the contenders - never mind about being a quick check on a result. I think this really _should_ qualify for an award! Regards Brian Beesley _ 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
Now, I'm going to toss out an idea. I thought about this a few minutes
after reading the previous message and I want to see if you all think its
worthwhile or not, or whether its even correct or not.
Here goes:
1) If we know the last n bits of a number x, then we can (easily) determine
the last n bits of x^2.
2) If we know the last n bits of x^2 we can easily determine the last n bits
of x^2 - 2.
3) It follows by repeating this (I hope) that we can (realatively easily)
determine the last n bits of the last number in the Lucas-Lehmer series.
Now the slightly sketchy part (provided that was all right) . . .
4) There are fewer than, or equal to, 2^n possible combinations of n
terminating bits when we examine the multiples of P = 2^p - 1, i.e. the
group {n_terminating_bits(P), n_terminating_bits(2P),
n_terminating_bits(3P), . . . }. It is my hope that this group has fewer
(ideally significantly fewer) than 2^n elements. That way if the last n
bits of the last term of the Lucas-Lehmer test is a combination of bits
which could not possibly be the final n bits of a product of P, then we know
that the residue cannot be 0.
Layman's example:
any number that ends in ...34587 cannot be divisible by 25. Why? (apart
from the obvious). Because any number that's a multiple of 25 ends in (now
I'm looking at the group {25, 50, 75, 100, 125, 150 . . .}), 00, 25, 50, or
75. ...34587 doesn't end with any of these.
I hope I've explained myself enough that you can either take from this any
worth which it might have, or correct the mistakes I've made. :)
Alex Healy
[EMAIL PROTECTED]
http://www.alexhealy.net
snip
*) Somebody finds a way to verify the output of the LL test
without a complete rerun (cf. verification of digital
signatures).
If this eliminates the need for double-checks, does it qualify?
That sounds interesting! Of course, if we could find a _quick_ way of
computing a few bits of the residual, we could use this as a filter
which would remove a large proportion of the contenders - never mind
about being a quick check on a result. I think this really _should_
qualify for an award!
Regards
Brian Beesley
/snip
_
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
Alex,
The group you seek always has 2^n elements. All bit combinations are
possible.
(P = 2^p-1 is "minus one" in n-bit words. 2*P is minus two, etc. up to
2^n*P which is 0. All bit patterns occur.)
Todd Sauke
Now, I'm going to toss out an idea. I thought about this a few minutes
after reading the previous message and I want to see if you all think its
worthwhile or not, or whether its even correct or not.
Here goes:
1) If we know the last n bits of a number x, then we can (easily) determine
the last n bits of x^2.
2) If we know the last n bits of x^2 we can easily determine the last n bits
of x^2 - 2.
3) It follows by repeating this (I hope) that we can (realatively easily)
determine the last n bits of the last number in the Lucas-Lehmer series.
Now the slightly sketchy part (provided that was all right) . . .
4) There are fewer than, or equal to, 2^n possible combinations of n
terminating bits when we examine the multiples of P = 2^p - 1, i.e. the
group {n_terminating_bits(P), n_terminating_bits(2P),
n_terminating_bits(3P), . . . }. It is my hope that this group has fewer
(ideally significantly fewer) than 2^n elements. That way if the last n
bits of the last term of the Lucas-Lehmer test is a combination of bits
which could not possibly be the final n bits of a product of P, then we know
that the residue cannot be 0.
Layman's example:
any number that ends in ...34587 cannot be divisible by 25. Why? (apart
from the obvious). Because any number that's a multiple of 25 ends in (now
I'm looking at the group {25, 50, 75, 100, 125, 150 . . .}), 00, 25, 50, or
75. ...34587 doesn't end with any of these.
I hope I've explained myself enough that you can either take from this any
worth which it might have, or correct the mistakes I've made. :)
Alex Healy
[EMAIL PROTECTED]
http://www.alexhealy.net
snip
*) Somebody finds a way to verify the output of the LL test
without a complete rerun (cf. verification of digital
signatures).
If this eliminates the need for double-checks, does it qualify?
That sounds interesting! Of course, if we could find a _quick_ way of
computing a few bits of the residual, we could use this as a filter
which would remove a large proportion of the contenders - never mind
about being a quick check on a result. I think this really _should_
qualify for an award!
Regards
Brian Beesley
/snip
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: The $100,000 award for 10,000,000 digit prime
7) Anyone that makes a mathematical or algorithmic breakthrough that speeds up the search process. I'm talking about a doubling in search speed not a 1% speedup in assembly code. I think that this would be great -- but I seriously doubt that any improvement will be found. We can't get any better with FP FFTs, since we don't have any zero-padding any more, and you've specifically disallowed implementational improvements. A switch to integer FFTs might be better for huge FFT lengths, but integer arithmetic is currently very slow compared to FP arithmetic, so I doubt that will end up helping. Really, the only hope I can see for a significant improvement is a really fast implementation of Schonhage-Strasen multiplication, but Schonhage-Strassn is almost infamously slow. I can dream of some possibilities. For example, somebody might find a way to easily detect whether Mp has an odd or an even number of prime factors, without revealing the factors themselves. We could reject all Mp with an even number of prime factors. If the test runs quickly, this could almost double the search time. Other potential improvements are borderline. For example, *) Somebody finds how to parallelize the FFT using little communication. The wall-clock time might be reduced 10-fold, but the CPU time increased 16-fold. This could be great for verifying a new Mersenne prime, but does it qualify for the money? *) Somebody finds a novel way to choose elliptic curves modulo Mp, using the information that its prime factors are == 1 (mod p) and that 2, -p are quadratic residues modulo any factor of Mp. This lets the trial division phase search 10 bits higher, such as searching to 2^74 rather than 2^64. Does its finder get any money? *) Somebody finds a way to verify the output of the LL test without a complete rerun (cf. verification of digital signatures). If this eliminates the need for double-checks, does it qualify? Peter Montgomery _ 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. -Chuck On Sat, 17 Jul 1999, Eric Hahn wrote: George Woltman wrote: Hi all, At the risk of opening Pandora's box, I'd like to bring up the possibility of splitting up the $100,000 award for a 10 million digit prime. I'm soliciting everyone's opinion before making a decision. 1/4 to George or charity (his choice) 1/4 to Scott or charity (his choice) 1/2 to the discover(s) or charity* *The discover(s) get to chose only if there is orderly exploration of exponents. Otherwise, it goes to a charity of their choice. That would be changed to 20%, 20%, 40%, and 20%, with the last 20% going to the individual(s) responsible for increasing the search speed significantly, if such event occurs. This promotes an orderly exploration of exponents, yet allows those who want to find a 10M digit prime just for fun (and unorderly) to have the opportunity without being completely penalized. It also encourages the advancement and development of new algorithms. This is all, of course, assuming a GIMPser is the discover(s)... _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- ~~~ : WWW: http://www.silverlink.net/poke : : E-Mail: [EMAIL PROTECTED] : ~~ : Ask Mike! Aviation's response to Dear : : Abby. http://www.avstarair.com: ~~~ _ 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: The $100,000 award for 10,000,000 digit prime
Hi all, At the risk of opening Pandora's box, I'd like to bring up the possibility of splitting up the $100,000 award for a 10 million digit prime. I'm soliciting everyone's opinion before making a decision. First off, it is by no means guaranteed that GIMPS will claim the award. Some have speculated that a search for Proth primes would have a better chance for success given equal computer power. Furthermore, version 19 will take over a year to test a single 10,000,000 digit number - so claiming the award is years away. However, a policy needs to be in place before version 19 is released. Secondly, I suspect splitting the award will require setting up a non-profit corporation. If I accept the award personally, I'd have to pay taxes -- no thanks. If there is anyone with useful insights on alternatives or how to set up and run a non-profit as cheaply as possible, please send me a private email. What follows is a possible list of beneficiaries along with a few reasons for or against: 1) A charity. There are several GIMPSers that are against any monetary awards. People should search for primes for love of math not the love of money. However, an all charity award could defeat the orinial donor's desire of encouraging advances in distributed computing. 2) Me. Some would argue that I share some of the credit for any Mersenne discoveries. Be aware that I will donate any share to charity. 3) Scott Kurowski. He has real expenses in running the PrimeNet server that should be reimbursed and has been instrumental in GIMPS' growth. 4) The discoverers of any Mersenne primes between now and the 10,000,000 digit discovery. This will encourage an orderly exploration of the exponents and keep up interest over the coming years. 5) The discoverer of the 10,000,000 digit prime. 6) Save some for Mersenne primes discovered after the 10,000,000 digit prime. This would be especially useful if the prime is discovered with lots of untested exponents below it. 7) Anyone that makes a mathematical or algorithmic breakthrough that speeds up the search process. I'm talking about a doubling in search speed not a 1% speedup in assembly code. Suggested rules for discussion on the mailing list: If you'd like to make a specific proposal (such as "all to charity" or "$50,000 for the 10,000,000 digit prime and $10,000 for all primes between now and then"), then send me PRIVATE email. Hopefully, I can form a consensus from these suggestions. Please use the mailing list for discussions on the benefits and drawbacks of the different choices. I can easily see this discussion getting out-of-hand with a corresponding increase in mailing list removal requests! Best regards, George Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: The $100,000 award for 10,000,000 digit prime
At 05:32 PM 7/17/99 -0400, George Woltman wrote: At the risk of opening Pandora's box, I'd like to bring up the possibility of splitting up the $100,000 award for a 10 million digit prime. 1/3 to George, or a charity of his choice 1/3 to Scott, or as he wishes, e.g. Entropia.com 1/3 to the discover(s) --Luke Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: The $100,000 award for 10,000,000 digit prime
George Woltman wrote:
4) The discoverers of any Mersenne primes between now and the 10,000,000
digit discovery. This will encourage an orderly exploration of the exponents
and keep up interest over the coming years.
You have anticipated my idea, George. The EFF awards should have been
structured this way to start with. Even better would be dividing equally
between George, Scott, discoverers of Mersenne 10^10^7, discover of
the first prime 10^10^7, and me. [kidding on the last part {8^D ] spike
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: The $100,000 award for 10,000,000 digit prime
Hi all, At the risk of opening Pandora's box, I'd like to bring up the possibility of splitting up the $100,000 award for a 10 million digit prime. I'm soliciting everyone's opinion before making a decision. I propose we split it like this : 33% to the finder of the first 10,000,000 digit prime, 33% to Scott and George, for doing excellent work 33% to charity, deciding by vote by all the members of gimps, every doublecheck gives an extra vote over factoring and LL-testing. Just an incentive to catch up on the doublechecking... Otto. _ 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
George Woltman wrote: Hi all, At the risk of opening Pandora's box, I'd like to bring up the possibility of splitting up the $100,000 award for a 10 million digit prime. I'm soliciting everyone's opinion before making a decision. 1/4 to George or charity (his choice) 1/4 to Scott or charity (his choice) 1/2 to the discover(s) or charity* *The discover(s) get to chose only if there is orderly exploration of exponents. Otherwise, it goes to a charity of their choice. That would be changed to 20%, 20%, 40%, and 20%, with the last 20% going to the individual(s) responsible for increasing the search speed significantly, if such event occurs. This promotes an orderly exploration of exponents, yet allows those who want to find a 10M digit prime just for fun (and unorderly) to have the opportunity without being completely penalized. It also encourages the advancement and development of new algorithms. This is all, of course, assuming a GIMPser is the discover(s)... _ 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
On Sun, 18 Jul 1999, Otto Bruggeman wrote: I propose we split it like this : 33% to the finder of the first 10,000,000 digit prime, 33% to Scott and George, for doing excellent work 33% to charity, deciding by vote by all the members of gimps, every doublecheck gives an extra vote over factoring and LL-testing. Just an incentive to catch up on the doublechecking... Ok, but who gets the leftover 1%? (I would vote me of course). Just had to go there, given the focus here bad math is just funny. First Law of System Requirements: "Anything is possible if you don't know what you're talking about..." _ 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
The EFF of course, is offering the prize to help the advancement of just this sort of distributed computing (well, in a simplified nutshell). I don't think anyone should "profit" from GIMPS, but if we were to win a huge prize, I think we should use the money as it's intended. The idea of giving money for people who come up with speed improvements or large contributions to prime theory is a good one, and certainly anyone that incurrs expenses (Scott, George... anyone) should be reimbursed... this is a small part of these prizes. Here are a few other off the wall ideas... they should be taken semi-seriously; more as an exercise in lateral thinking than anything else. Beyond giving out the money in our own way, we could use it to increase GIMPs computing power in a few ways. If we started a non-profit organization, we could buy our own server farms with the money... Hell, we could double our speed right now by spending $50,000 on vanilla pentiums, a room, and a huge electric bill. I bet a few people on the group would volunteer time to keep it up. When the money runs out, donate the computers to a school or something; even then, the money then becomes well spent on continuing the computer industry, within parallel computing, and within education; a worthy cause. Or this... pay a computer manufacturer to subsidize computer sales to academia with the requisite that the Prime95 (or similar) software is installed ahead of time? Or just donate money to high-schools or colleges to buy computers with the requisite that they help the GIMPs project? Again, everyone wins, and noone feels greedy. OR... we could fund the production of sieving/LL testing hardware. I'd like to see a four inch square cube sitting on my desk running factor.exe all day. :-) Advertise... could you imagine advertisements for GIMPs in the Wall Street Journal? :-) Or a good spot on Cartoon Network or the Sci Fi Channel. 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 could go on... but I imagine this is long enough, and people probably won't make it much further. Just some ideas. I admit, tho, that although I'm not completely sure what happend to the current prize money, everyone on the project should at least have a vote or a word in a discussion about what happens to it. Later, ---Chip \\ ^ // (o o) ---oOO--(_)--OOo | Chip Lynch| Computer Guru| | [EMAIL PROTECTED] || | (703) 465-4176 (w) | (202) 362-7978 (h) | _ 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
Chip Lynch wrote:
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.
Great idea Chip! I think there's a bunch of GIMPSers that hang out
in Santa Clara county or SF Bay area. We could do something that
wouldnt cost anything, like a potluck picnic at a local park, or a group
hike or just a social gathering. We could see if Scott wanted to come,
and if he showed up we could wax his car, or carry him off the field
on our shoulders, that sorta thing. {8^D Ideas? spike
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
