Computer Science Canada GIMPS - The Great Internet Mersenne Prime Search |
| Author: | the_short1 [ Thu Jul 27, 2006 6:38 pm ] |
| Post subject: | GIMPS - The Great Internet Mersenne Prime Search |
Hey fellow compsci'ers... Recently, while doing research for a Project Euler math/programming contest i stumbled on this: http://www.mersenne.org Basically, the world is out to find the next largest prime number, and mersenne primes are a special type, and currently, only 43 exist! And the largest known prime is mersenne and its 9,152,052 digits long!!! It was found in december 2005... if the next prime is >10mill digits, a $100,000 prize is at stake!!!! WHY ??? What is GIMPS? Its a multinational collaborative project to unify computers to help find the next prime. ARE YOU AN OVERCLOCKER?? This is a good stress test program! You download this small application that runs in the background (you can specify the times to let it run, the ammount of ram, and which cpu *if ya have dual/core*)... it runs at LOWEST priority, meaning it will NOT AFFECT COMPUTER USAGE!!! the momment you go to run another program, Prime95 (the program), gives up all the CPU to the program you want to use... But while your computer is idle, it uses 100% cpu.... Ive been doing it for about a week now.. and im 10% done one exponent...(its sched to finish august 29th)... yes it takes THAT long.. but this is for good cause.. and theres a PRIZE!!! If your exponent produces a prime that has over 10mill digits, you will get up to $50,000 of the prize!!!!! It connects to the internet once and hour for less then 3 seconds, basically to update the server with your completion date for your exponent, each person gets a unique exponent to test. I leave it running while playing Doom3..etc.. and it doesnt lag . and i have it set to 50MB RAM during the day.. 200MB at nite.. . but the default is (8MB), i just jacked mine up to make it faster. I get about 0.082 s per interation and im testing an exponent >33mill!! Ok... now your thinking you need a fast computer for this.. .NOPE... Even if you have a pent1, you can contribute.. . this program does work based on your cpu, the better you have the better you can help. If you have a crappy computer, you will get to re-test numbers/small number factoring, etc. EDIT: You can check your rank against others (cpu time donated), and you can form teams too! As well you can send in your benchmarks for there benchmark page and compare your interation times to other rigs like yours. Just check out the website.. it can explain it better then me. -Kevin |
|
| Author: | Cervantes [ Thu Jul 27, 2006 7:25 pm ] |
| Post subject: | |
the_short1 wrote: but this is for good cause..
Is it really? Things like these are researched because they are a challenge. It's like computing Pi. We don't actually need Pi to millions of digits: Wikipedia wrote: There are few, if any, cases in engineering and science where more than a few dozen digits are needed; with the 50 digits given here, the circumference of any circle that would fit in the observable universe (ignoring the curvature of space) could be computed with an error less than the size of a proton.
Grid computing is great, but it's best when done for a good cause. Calculating primes? Look, I'm one of the mathiest types there are, but I still can't throw my support behind this. World Community Grid, to help find a cure to AIDS or to compute the human Proteome, gets my support. |
|
| Author: | the_short1 [ Thu Jul 27, 2006 7:39 pm ] |
| Post subject: | |
Cervantes wrote: ........World Community Grid, to help find a cure to AIDS or to compute the human Proteome, gets my support.
OK.. that seems like a much better cause  .... i wasnt aware of that one.. i have heard about Folding@home a lonngg time ago.. but i forgot about that one too. Ill look into the aids one later tonite.
Albeit this one has the potential to acually get recognition for you efforts. and its geeky math fun  |
|
| Author: | Cervantes [ Thu Jul 27, 2006 8:00 pm ] |
| Post subject: | |
the_short1 wrote: Albeit this one has the potential to acually get recognition for you efforts
True. But if this is as popular as World Community Grid, your odds of finding the right one are just as low. So let's say you've got the same chance of "winning": you get to pick either A) $50,000 or B) being the person who, in part, found the cure for AIDS. Which would you choose? Choosing A) is being a sellout.  |
|
| Author: | md [ Thu Jul 27, 2006 9:07 pm ] |
| Post subject: | |
or ya know... you can run more then one app... if they both run at the lowest priority then they will just share processing time. Primes are actually important though, if anyone could come up with a way of predicting prime numbers accurately (and quickly) most (if not all) modern encryption techniques would fail. |
|
| Author: | Cervantes [ Thu Jul 27, 2006 9:19 pm ] |
| Post subject: | |
Cornflake wrote: Primes are actually important though, if anyone could come up with a way of predicting prime numbers accurately (and quickly) most (if not all) modern encryption techniques would fail.
So what you're saying is its important not to research primes?
Heh, don't worry. I understand. This sounds awfully the same as what they say about quantum computers. Is that because a quantum computer could generate a huge amount of primes very quickly? |
|
| Author: | md [ Thu Jul 27, 2006 10:11 pm ] |
| Post subject: | |
Cervantes wrote: This sounds awfully the same as what they say about quantum computers. Is that because a quantum computer could generate a huge amount of primes very quickly?
Kinda, mostly there are algorithyms that have already been designed to take advantage of the way quantum computers work that will factor any number in in effect O(1) time. If you can find the prime numbers used to generate hte private/public key pair you can duplicate both keys and break the encryption. Quantum computers will radically change the security landscape. |
|
| Author: | the_short1 [ Thu Jul 27, 2006 11:58 pm ] |
| Post subject: | |
Yea.. lucky us... u of waterloo is heading up the field in quantum computing.. they just got a 500k$ grant a few months back for there quantum computing division.. Yea i see what ya mean cervantes.. i want to find one for cancer if one exists... i just found out my cousin has cancer.. @ age 27  ..... maybe ill have 3 going... 33% of a amd 3300+ is still a decent chunk.. (800MHz each)...
You also get your name in the world record books for worlds largest prime found by xxxxx ..... @Cornflake.. i never though about the security aspects of quantum... its going to be an interesting few years during the transition.. on topic of encription.. . doing the project euler contest.. one of the questions is brute forcing using XOR on a whole document with a 3 letter key.. its quite fun |
|
| Author: | md [ Fri Jul 28, 2006 1:46 am ] |
| Post subject: | |
the_short1 wrote: Yea i see what ya mean cervantes.. i want to find one for cancer if one exists... i just found out my cousin has cancer.. @ age 27
..... maybe ill have 3 going... 33% of a amd 3300+ is still a decent chunk.. (800MHz each)...
@Cornflake.. i never though about the security aspects of quantum... its going to be an interesting few years during the transition.. on topic of encription.. . doing the project euler contest.. one of the questions is brute forcing using XOR on a whole document with a 3 letter key.. its quite fun Bad luck 'bout the cousin. You're misconceptions about relation between processor cycles and CPU power is quaint however. Clock cycles per second is an almost meaningless measure of CPU speed. However, yes one third the processing power of an AMD 3300+ is still a decent chunk of power. In hte end it's a drop in the bucket, but that's more then no drop. XOR encryption is a joke. I wrote a brute force cracker in grade 11 programming, great fun. RSA and other similarly designed public/private systems are where the real interesting stuff is, as well as certain block encryption cyphers (blowfish and twofish for example). These beasts are WAY harder to crack then most people could even think about; but with a quantum computer though cracking them is easier then breaking a leg with a cannon. On the plus side quantum mechanics also gives us perfectly secure communications. Highly expensive, but infinitely secure; 'cept from dumb people... but then they are aways hte weakest link anyways. |
|
| Author: | [Gandalf] [ Fri Jul 28, 2006 9:08 am ] |
| Post subject: | |
It seems that the WCG has a new project you can participate in, "Help Defeat Cancer", so that should solve one of your difficulties. 
Quote: Help Defeat Cancer (Launched July 20, 2006)
World Community Grid and The Cancer Institute of New Jersey, Rutgers University and UMDNJ - Robert Wood Johnson Medical School will be examining Tissue Microarrays to determine how to improve the treatment of cancer with earlier and more targeted diagnostic tools. |
|
| Author: | the_short1 [ Fri Jul 28, 2006 10:46 am ] |
| Post subject: | |
Thanks gandalf Ok, well, i think i will hold off on aids until august 30th once my exponent is done, then thats one month+ contribution to prime land, factoring out one whole (posible) prime 
@Cornflake..jc.. how old are ya ?..(i just noticed your at u of W, that would explain how you know a lot about quantum ). yes you have to think about the FSB, cache, core architecture, features such as sse3... etc.. |
|
| Author: | md [ Fri Jul 28, 2006 11:10 am ] |
| Post subject: | |
the_short1 wrote: @Cornflake..jc.. how old are ya ?... yes you have to think about the FSB, cache, core architecture, features such as sse3... etc..
I'm old, really really old. And smart, smarter then most people anywhere. And no, features do not have a major impact on performance. SSE, SSE2, SSE3 and MMX are all simply faster ways of doing floating point arithmatic in certain cases. |
|
| Author: | bugzpodder [ Sun Jul 30, 2006 12:40 pm ] |
| Post subject: | |
Cornflake wrote: or ya know... you can run more then one app... if they both run at the lowest priority then they will just share processing time.
Primes are actually important though, if anyone could come up with a way of predicting prime numbers accurately (and quickly) most (if not all) modern encryption techniques would fail. good luck! that'll never happen. |
|
| Author: | bugzpodder [ Sun Jul 30, 2006 12:44 pm ] |
| Post subject: | |
Cornflake wrote: Cervantes wrote: This sounds awfully the same as what they say about quantum computers. Is that because a quantum computer could generate a huge amount of primes very quickly?
Kinda, mostly there are algorithyms that have already been designed to take advantage of the way quantum computers work that will factor any number in in effect O(1) time. If you can find the prime numbers used to generate hte private/public key pair you can duplicate both keys and break the encryption. Quantum computers will radically change the security landscape. actually, no, it couldnt be more further from the truth. If this is possible, then we can do *ANYTHING* finite in O(1) second. which is ridiculous. if a quatum computer with a reasonable number of quantum bits exists (what, 20? 30? 40?), what effectively happens is we simply needs like 10x the size of the primes/numbers in the crytography algorithms in order for them to be unbreakable. factoring is hard! If you have a O(n^p) time algorithm for factoring (even on a quantum computer) then you'd probably be richer than bill gates. |
|
| Author: | bugzpodder [ Sun Jul 30, 2006 12:49 pm ] |
| Post subject: | |
okay i did a bit of search on quantum factoring, it seems the best algorithm is O(n^2) where n is the size of the input so its much better than I expected. But it is certainly not even close to O(1). |
|
| Author: | md [ Sun Jul 30, 2006 4:40 pm ] |
| Post subject: | |
I have not read anything new about QC's is a while, but iirc most of hte speed of the algorythm came from performing it on large sets of data at once. 'Course I could indeed be wrong, and it could be that factoring a number would take O(n^2). Even at O(n^2) though encryption becomes iffy, yes you could use larger primes and keys, but then someone could just as easily build a larger computer. Already with distributed computing breaking keys isn't as hard as people think. Difficult and not practical without a large number of super computers, but not impossible. |
|
| Author: | bugzpodder [ Sun Jul 30, 2006 8:57 pm ] |
| Post subject: | |
first of all, looking at execution time on a specific set of data has no meanign what so ever in terms of Big-O notation. secondly O(1) algorithm means that regardless of size of data, your algorithm would take essentially the *same* amount of time. I am not even sure if you understand what O(1) means. Factoring is O(1) is like saying: I dont care what number you give me, I can factor it in one second, which is a ridiculous statement. Also, it takes no more than 10 seconds to find out that factoring takes O(n^2) time on a quantum computer using google, so it would be benificial if you might have done so instead of still claiming factoring would take O(1) and that empirical evidence suggests that, rather than having me checking your claims by looking it up. secondly, parallel computing does NOT usually reduce the asympotic runtime of an algorithm. This is because you are using a finite number of computers N, and since amount of work is constant M, you can speed up your algorithm by a factor of N at most. However, it is possible that you design your algorithm cleverly enough to increase the speed by about log log n usually, such as i think sorting takes n log n/log log n using parallel algorithms. I think the current qubit in a built quantum computer is like 8 bits. so essentially if we have primes that is larger than the storage/computation space of such a quantum computer, we are safe. After all, we cant hold a lot of information with just 8 bits, right? |
|