Why the search for ever larger primes? - MathOverflow

Why the search for ever larger primes?

2009-10-17T18:24:11Z

I understand why primes are useful numbers and also why the product of large primes are useful such as for application in public key cryptography, but I am wondering why it is useful to continue the search for larger and larger prime numbers such as in the GIMPS project. It would seem to me since that since it already proven that there are an infinite number of primes, I am not quite sure why working to finding bigger and bigger really matters!? Is this a "Climbing Mt Everest because it is there" kind of thing, or is the search and finding bigger results somehow furthering mathematics in some kind of way?

Answer by Quadrescence for Why the search for ever larger primes?

2009-10-17T18:38:09Z

I used to do very large computations of pi, and even wrote several programs to do it. I see this as analogous to computing (a) the primality of large numbers, and (b) finding very large primes. I computed pi because, well, it was fun! There was no practical reason to do so. Sure, I could do some statistical tests on the digits or search for my phone number and date of birth in the string of digits, but otherwise it was just an endeavor in pushing my hardware to its "computational limits" and combining what I know about programming and mathematics to make some integrated product (no pun intended).

So, while I can't speak for the prime number crunchers, I believe it is just done "just because". It also gives an avenue to try new and more efficient numerical algorithms for multiplication and related operations, since the programs that compute large primes use these algorithms extensively.

Edit: In response to the part about there being an infinite number of primes, while there certainly are an infinite number, generating the Nth prime isn't a trivial task (while, for example, computing pi to a million decimal places is a trivial task). There are "prime number formulas" that can give one the Nth prime directly and deterministically, but these algorithms/formulas are incredibly inefficient, usually derived from Wilson's theorem. Mill's theorem provides another prime number formula, but requires the value of a certain constant called "Mill's constant". But to find that constant, you must find primes beforehand (this doesn't make Mill's theorem irrelevant, just not useful for the computation of primes).

Answer by Reid Barton for Why the search for ever larger primes?

2009-10-17T18:53:02Z

Well the M in GIMPS stands for Mersenne, and it hasn't been proven that there are infinitely many Mersenne primes. But it's widely believed to be true--in fact there is a conjectural estimate of their frequency. I think the search for Mersenne primes is mostly a "because it is there" thing, but it could provide numerical evidence for or against this conjecture.

GIMPS is probably more interesting as an experiment in massively distributed computation.

Answer by thinkhard for Why the search for ever larger primes?

2009-10-17T19:04:32Z

There are actually many reasons why the search for ever larger prime numbers continues even after 2300 years. Foremost it is applied number theory, secondly you can win prize money to further your research! There are also ancillary benefits such as advances in distributed computing algorithms, much like CERN (pursuing particle physics) created HTML, HTTP the first web server and the first web browser from the practical need to share information. Sure, there is a Mount Everest appeal to finding the biggest prime, but is actually about the development of ever efficient algorithms to find them. This yields greater insight to time and space complexity in computer science and computing known primes (or unknown for that matter...) can be a good benchmark for new hardware.

Answer by Jason Dyer for Why the search for ever larger primes?

2009-10-20T22:06:21Z

There was a significant real-life effect to the effort to discover primes: it was how the infamous Pentium bug was discovered.

Professor Thomas Nicely, then a professor of mathematics at Lynchburg College, had written code to enumerate primes, twin primes, prime triplets, and prime quadruplets. Nicely noticed some inconsistencies in the calculations on June 13, 1994 shortly after adding a Pentium system to his group of computers, but was unable to eliminate other factors (such as programming errors, motherboard chipsets, etc.) until October 19, 1994. On October 24, 1994 he reported the issue to Intel. According to Nicely, his contact person at Intel would later admit that Intel had been aware of the problem since May 1994, when the flaw had been discovered when testing the FPU for its new Intel P6 core, first used in the Pentium Pro.

Answer by Michał Kukieła for Why the search for ever larger primes?

2010-01-30T18:34:42Z

The question is answered to some extent in The Prime Pages FAQ.

Answer by Douglas S. Stones for Why the search for ever larger primes?

2010-01-31T04:41:30Z

While it is true that primes are useful such as for application in public key cryptography, you won't be using the largest known primes for such tasks -- that is much too impractical.

I have discovered some large primes in the past (see my prime search profile: http://primes.utm.edu/bios/page.php?id=776), which made a cute little addition to my CV.

It's probably also a popular pursuit because it's so easy to understand the concept of primality, that there's always a larger prime, etc. Lots of people can understand "I found the X-th largest known prime!"