mersenneforum.org New to GIMPS? Start here!!!
 Register FAQ Search Today's Posts Mark Forums Read

 2003-11-30, 23:19 #2 Prime Monster     Aug 2002 22×5×13 Posts What is GIMPS? The Great Internet Mersenne Prime Search, also known as GIMPS, is a prime example of Distributed Computing project at work and no pun intended. The goal of the GIMPS project is to discover new Mersenne Prime numbers. Mersenne primes are named after Marin Mersenne, a French monk and mathematician, who was born in 1588. Mersenne investigated a particular type of prime number: 2P-1 (2 to the power of "P" minus one), in which "P" is an ordinary prime number. (How to pronounce Marin Mersenne) Mersenne primes are much rarer than ordinary primes, of which there are an infinite number. The GIMPS effort, exhaustively searching for possible candidates since 1996, has been responsible for discovering the six most recent examples. Altogether, in all of history only 41 Mersenne Primes have been discovered, and GIMPS have discovered the 7 largest. GIMPS was formed in January 1996 by George Woltman, as one of the first open Distributed Computing projects, to discover new world-record-sized Mersenne primes. All the necessary software can be downloaded for free. Most GIMPS members join the search for the thrill of possibly discovering a record-setting, rare, and historic, new Mersenne prime. All you have to do to be part of it, is to contribute spare or idle CPU cycles. Pretty cool. I emphasise that you do not need to be a mathematician to take part in GIMPS, in the same way as you do not need to be a mechanic to drive a car. It is one of the few projects where ordinary people can contribute to fundamental scientific research. Last fiddled with by Prime Monster on 2004-05-29 at 13:13
 2003-11-30, 23:21 #4 Prime Monster     Aug 2002 22×5×13 Posts What is Distributed Computing? Distributed Computing (DC) is a branch of Computer Science that tries to solve large problems by giving small parts of the problem to many computers to solve and then combining the solutions for the parts into a solution for the complete problem. Distributed Computing projects have been designed to use the computers of hundreds of thousands of volunteers all over the world, via the Internet, to look for extra-terrestrial radio signals, to look for prime numbers so large that they have more than ten million digits, and to find more effective drugs to fight the AIDS virus. These projects are so large, and require so much computing power to solve, that they would be impossible for any one person, computer or even a large corporation to solve in a lifetime. Also see the post More on Distributed Computing Last fiddled with by Prime Monster on 2003-12-01 at 19:24
 2003-11-30, 23:22 #5 Prime Monster     Aug 2002 22×5×13 Posts A little bit of history The study of Mersenne primes has been central to number theory since they were first discussed by Euclid in 350 BC. The man whose name they now bear, the French monk Marin Mersenne (1588-1648), made a famous prediction about which values of "P" would yield a prime. It took 300 years and many important discoveries in mathematics to prove his conjecture. Prime numbers have long fascinated amateur and professional mathematicians alike. In the past fifty years a number of individuals wrote software and developed databases to aid in the search for Mersenne primes. Slowinski of Cray Research comes to mind among several others. But it wasn't until late 1995, when George Woltman gathered up the disparate databases and combined them into one, it really took off. In early 1996 George placed this database, and a free and highly optimised program to search for Mersenne primes, on the Internet to coordinate the search; the start of the Great Internet Mersenne Prime Search. The first version of GIMPS was based on using manual reservation of exponents and manual reporting of results. You can still use this method today, but most participant use the automatic method that was introduced with PrimeNet. PrimeNet was established in late 1997 by Scott Kurowski (and others) to automate the selection of ranges and reporting of results for GIMPS. When the project began, there were only 40 people and a little over 50 computers using their spare CPU cycles; the project has since grown to thousands of users and computers. The software has also changed quite a bit from GIMPS's beginnings; The factoring part of the program was originally written for 386 computers, in its current incarnation it detects the processor type and, if possible, uses hand-coded support for the P4's SSE2 codeset. Another aspect of the software, which probably influenced how the project is set up and managed, is that at first, there were many errors in checking for the primes, and all discovered Mersenne primes had to be double-checked to ensure their validity. Even today every result, whether a prime or not, is double-checked, as errors are still occurring. Current estimates are that the error-rate is actually increasing slightly. GIMPS is a unique distributed computing project for many reasons. George Woltman publishes the GIMPS software source code, and welcomes anyone to revise the software or make enhancements, as long as they follow the GIMPS rules. And, although the source code has been fully released, there doesn't seem to be any threat of data contamination that is present in some other distributed computing projects. If the results indicate a prime number, other users could check the same exponent and verify that it is a Mersenne prime, and given the prize and fame a discoverer gets, it seems unlikely that someone who found a Mersenne prime would keep the discovery hidden. Last fiddled with by Prime Monster on 2003-12-01 at 19:29
 2003-11-30, 23:23 #6 Prime Monster     Aug 2002 22·5·13 Posts A tiny bit of theory An integer greater than one is called a prime number if its only divisors are one and itself. The first prime numbers are 2, 3, 5, 7, 11, etc. A Mersenne prime is a prime of the form 2P-1. The first Mersenne primes are 3, 7, 31, 127, etc. In 1644 Mersenne claimed that n is prime if P = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 and 257 but composite for the other 44 primes smaller than 257. Over the years it has been found that Mersenne was wrong about 5 of the primes less than or equal to 257 (he claimed two that did not lead to a prime (67 and 257) and missed 3 that did: 61, 89, 107). The Mersenne primes are not just pretty numbers, though: they do have many applications. The most common uses for these primes are for forming algorithms, and, interestingly enough, testing hardware (Check towards the end of the page). To show that a small number is prime, we can just divide by the primes below its square root. For example, 53 is prime because it is not divisible 2, 3, 5 or 7. Large numbers need more complicated tests that usually involve a form of LaGrange's theorem. If you look at a list of the largest known primes you will see that for most such numbers n, either n+1 or n-1 factors easily. Mersenne primes follow this rule and are the primes of the form 2P-1. It is easy to show that p here must also be a prime, (at least that is what the mathematicians tell us). Because of the special form of the Mersennes, there is an easy test to see if they are prime, called the Lucas-Lehmer test. Last fiddled with by Prime Monster on 2003-12-01 at 01:22
 2003-11-30, 23:24 #7 Prime Monster     Aug 2002 22·5·13 Posts Some words about the Work and the Client Prime95 is a free program written by George Woltman and provided on his GIMPS site. Just download the software, install it, and let it run. Simple and easy, but the road is long. GIMPS is not a project for the faint at heart, most of the exponents (work units), depending on type of work you choose to do, are huge! Over 86% of those who have begun to test a Mersenne exponent with GIMPS have never completed even one, and the average GIMPS participant has completed less than three (mean 2.67). GIMPS appeals to those with a lot of patience, the work units take a lot of crunching, but pack serious punch. Very friendly to offline operation and P4's, and runs well on a wide range of x86 machines. Finding a Mersenne prime is no easy task; a first time primality test for a single candidate exponent takes a fast machine three to four weeks, running 24/7. On the fastest Tbirds, PIII's, and P4's, prime95 performs better, due to the SSE2 optimizations in the code. This is without a doubt one of most process intensive project in all of computing. A test runs through three phases before the result is considered final, done gradually and by several different machines. First, each candidate exponent goes through a level of trial factoring, which is a brute force approach designed to eliminate non - prime candidates early on in the process. This works by checking the number for small divisors, using the fact that factors of Mersenne numbers are of the special form q = 2kp+1, and that testing a factor candidate simply requires a binary powering, i.e. one finds 2p modulo q (which involves roughly log2(p) arithmetic steps on numbers no larger than q2) and checks if the result is equivalent to -1 modulo q. One can also do a small amount of factoring work using (say) Pollard's p-1 method or the elliptic curve factorizations method, both of which involve manipulating numbers the size of the Mersenne number itself. If no factors are found then the exponent is released for a first time Lucas - Lehmer primality test. A final double-check is done later by another computer to verify the validity of the result. This project has it advantages, namely the client itself. This has to be the most stable, mature, feature rich DC client on the net. It will use as much or as little memory as you allow it, and will get completely out of the way whenever another program needs cycles. It can be run as a service, completely hidden from view, with the ability to run when the user logs off so no cycles are wasted. Client Highlights[list=1][*]Mature client[*]Easily runs when logged off. Just check Run at Bootup. You need not know about Windows services![*]Caches work automatically, so it keeps going if offline. No helper programs are needed to cache work for it.[*]Low memory needs so PCs with modest RAM can use it. If you are short on RAM you can still run it. (2% of the time it wants more RAM for P-1 and the user can set limit.)[*]Low bandwidth needs: <~1 KB / month. Great for dial-up![*]Stringent verification within each run and across runs, so you know your CPU cycles are not being wasted.[*]GIMPS offers something that many other distributed projects don't: actual regular discoveries[*]A very responsive developer, George Woltman, who frequents this board as Prime95[/list=1] Last fiddled with by Prime Monster on 2003-12-01 at 21:58
 2003-11-30, 23:24 #8 Prime Monster     Aug 2002 4048 Posts Monetary Awards As if having the best Distributed Computing client on the net is not a big enough incentive to run GIMPS, there is also a substantial award for the person that discovers a ten million digit prime number. The Electronic Frontier Foundation is offering a $100,000 award, see the EFF Cooperative Computing Awards, to the first person or group to discover a ten million digit prime number. If you find such a prime with the software provided, GIMPS will claim the award and distribute the award according to the rules published on the GIMPS site. A Word of Warning!!! If you decide to install this client, or any other DC client, on your employers machines, always, always get written permission before installing idle-cycle software on any machines you do not have absolute administrative control over. Many companies have a strict policy against running any non-business software. You will not get a lot of sympathy from the DC community if you installed a DC client on a lot of machines and then got into trouble because of that. In some countries it is actually a criminal offence. Last fiddled with by ewmayer on 2006-06-04 at 19:16 Reason: updated EFF co-op awars link  2003-11-30, 23:25 #9 Prime Monster Aug 2002 22·5·13 Posts The type of work you can do You have the choice of 4 different types of work units you can do for the project. The client can also do other types of work as well, but they are outside the scope of this page (for more information see the readme.txt that comes with the client and the Other Projects section on this board). [list=1][*]Factoring of a prime number (exponent) candidate This is a pre check of a candidate exponent. These work units take the least time and are given out by the server according to your CPU speed. They may go through several iterations of bit length before clearing and getting sent to a fast machine for the more intensive Lucas-Lehmer testing. This is best for low-end PIIIs and Athlons[*]Double checking a prime candidate Double checking is done to work units which have cleared one round of LL testing. This verifies that the LL test has concluded correctly and ensures that the CPU of first running conformed to spec. These are small to medium units, PIII, Athlons and low end P4s turf here. Basically this is a Lucas Lehmer test, but the exponent size is smaller than for the current first time primality test range. [*]Lucas Lehmer (LL) testing on a prime candidate These candidates are much bigger than the run in the double testing pool. It is a virgin run; the chance of finding a prime candidate is about 1 in 100 000. Pre factoring ensures that no time is spent on lengthily LL work when a simple factor is present.[*]10.000.000 + digit Mersenne prime LL testing This is the grand daddy of all DC WU - only the diehard crunching fanatic need apply. Depending on the size and your box, several months to a year (and even more) of CPU time is needed. Same as above except for size and one other thing: the prize. Find one of these and you win a substantial prize, something like over 50.000$ US\$ - enough to cover a good bit of D. Find the first one and you will live forever in mathematics history.[/list=1] Last fiddled with by Prime Monster on 2003-12-01 at 19:30
 2003-11-30, 23:26 #11 Prime Monster     Aug 2002 22·5·13 Posts How to set up a Team The GIMPS project does not really support teams like other Distributed Computing projects. This does not mean that it is impossible to have teams, it is. GIMPS uses a nice little trick to get teams to work, and that is to use the User ID field for the team name. So, if you want to set up a team for you and your friends, you will have to specify this when registering from one of your clients. Tick the CheckBox to create a team. Note: You will only have to do this once. Name and e-mail address remains individual for each computer. Anyone that wants to be a member of your team must then use the same User ID (Team name) and password. It is quite smart to use different Computer IDs for each computer, so it is easier to identify the individual member. Each computer gets its individual tasks and can individually be set to special task types under "Test, PrimeNet". Besides possible psychological effects of competition, building a team has no impact on how soon a task is done. Nevertheless, building or joining a team can be fun, as you get in contact with other people, can find friends and equal-minded people that share the same interests as you. Last fiddled with by Prime Monster on 2003-12-01 at 19:32

 Similar Threads Thread Thread Starter Forum Replies Last Post christian_ Information & Answers 9 2016-01-22 19:28 jasonp Operation Kibibit 65 2013-09-03 22:06 Thomas11 Lone Mersenne Hunters 29 2008-12-21 13:47 ValerieVonck Marin's Mersenne-aries 8 2006-04-29 22:21 OmbooHankvald Factoring 15 2005-09-03 13:42

All times are UTC. The time now is 01:36.

Tue Sep 22 01:36:28 UTC 2020 up 11 days, 22:47, 0 users, load averages: 1.61, 1.41, 1.48