9

It always takes a lot of effort and money to find the next largest prime number. Why is it so important to do this work and what is the application those numbers?

Ali
  • 1,399
Mohsen
  • 227

6 Answers6

7

Reason number 1: scientific curiosity.

Reason number 2 (the economic reason): The RSA encryption algorithm requires large prime numbers to make secure data transmissions. The larger the primes, the more secure the transmission.

icurays1
  • 17,161
  • 13
    The largest known prime seems to satisfy almost zero scientific curiousity, IMHO, any more than finding the largest known integer does. It seems mostly to be about bragging rights. – Thomas Andrews Jul 14 '13 at 22:24
  • Indeed, the largest known primes might not be publicly known, if discovered by some intelligence agency. – celtschk Jul 14 '13 at 22:24
  • 11
    RSA doesn't require primes as large as the largest known primes, or even close to that. The current largest known prime has over 10 million digits, which is way more digits than would be useful for RSA or any other (publicly known) encryption scheme. – Thomas Andrews Jul 14 '13 at 22:27
  • @ThomasAndrews You're probably right - unless factorization methods or hardware are vastly improved in the near future, which is probably unlikely. I suppose it really is just for bragging rights! – icurays1 Jul 14 '13 at 22:34
  • 5
    Isn’t the whole point of the primes used in RSA that there are so many other primes of roughly the same size known? If there are some isolated high primes out there used in RSA, they’d be pretty easy to guess and then the whole algorithm would be useless (unless they are really unknown to others as in not even known be prime). And if you look at the public key, you can tell whether a very large prime has been used or not, since it then must be even larger. – k.stm Jul 14 '13 at 22:49
  • @K.Stm. To my (admittedly limited) knowledge, the point is that factorizing large composite numbers is hard, particularly when the composite is the product of two large primes. – icurays1 Jul 14 '13 at 22:52
  • 1
    @icurays1 Yeah, my point is: If there was a very big prime used, then this would be obvious from the size of the public key. If there aren’t that many large primes, but a rather manageable list of known big primes, you can simply use trial and error to factorize the public key. – k.stm Jul 14 '13 at 22:55
  • 1
    @K.Stm. For RSA it suffices that a number is very likely to be prime, e.g., with probbaility $1 - 2^{-k}$ for some large $k$. So in those applications it suffices to pick a random huge number and apply some fast probabilistic prime-testing algorithm to test whether this number is likely to be prime, and so it's easy to generate a big list of likely primes of this size. But yeah, if you knew that a definite prime was used, then you would need a big list of large primes for this to be useful. – TMM Jul 15 '13 at 19:12
  • @TMM: I've never thought about it deeply, but there's the question whether the RSA algorithms actually work if I use two numbers of which one isn't actually a prime but was only shown to be very likely prime. And then I thought: Of course the RSA algorithm will work at least most of the time, because otherwise you could run it, and if it fails you've shown that one of your factors is composite! – gnasher729 May 21 '14 at 20:31
6

Just to add to the previous answers: Usually, part of the discovery of these mathematical curiosities is not the result itself, but the new or improved method for finding these new results. It's not just about finding the number which is meaningless in itself, but it's about showing that mathematical techniques have advanced so much that we can even show that these incredibly huge numbers are prime.

Similarly, who cares that we planted a flag on the moon, or that we sent people there at all? It's all about showing that we can do this.

TMM
  • 9,976
  • 4
    Well it is kind of boring when you have found an asymptotically optimal algorithm, the only improvements are in hardware or neat arithmetic tricks. At least in my opinion. – Thomas Jul 15 '13 at 02:40
3

Because they're there.

Euclid called our attention to the fact after "because" in the third century BC, and Hillary called our attention to the appropriateness of "because" in the 20th century AD.

Also, large primes play a role in cryptography, which protects your bank P.I.N. number from thieves.

Michael Hardy
  • 1
1

Re the original question: I'd hazard a guess that, for almost the entire world, the question 'why' simply wouldn't arise, since the work makes zero contribution to their welfare and the future of humanity. It's probably safe to assume that it has subjective value for the few who engage themselves in the task.

Al Catraz
  • 11
1

Finding Primes is basically a giant benchmark and test platform for large computers and distributed computing systems. It has several advantages as a benchmarking and experimental problem

  1. Its a simple and well understood problem (Is this number prime? No, ok next one)
  2. There are many potential algorithms that can be directly compared
  3. Its simple enough that it can be run on any computational machine, providing a standard benchmark for performance

Think of it as a "test-system" for computer scientists. By learning how to efficiently distribute work over millions of computers to find something like the next largest prime, we can research new techniques for doing so more efficiently. Imagine a more complex problem, like weather prediction, here we not only need to figure out a good algorithm to solve such a complex system, but also how to distribute it efficiently. Through research on primes and other simple (as in, well defined) computational problems, the first part is basically taken care of, we can learn to more efficiently corral computers to solve large problems. Because its so easy to objectively analyze the difference in efficiency (literally, how long it takes), we can compare the relative merits of different distribution schemes, both in software (multithreading) and in hardware (different memory/system architectures).

As for research into prime algorithms themselves, being able to find large primes is needed for most canonical encryption schemes, larger primes are harder to factor and therefore more secure. Its also a research field in number theory.

As for specific projects dedicated to finding primes, I'd wager that its just out of general curiosity and competition.

crasic
  • 4,849
0

This question presumes that finding large prime numbers is important, which is of course dead wrong. After all mathematics is all about proving theorems, simply knowing that some large number is prime is of no value whatsoever. Doesn't tell you anything. And apart from this, the widely shared opinion is that this is second-rate work, as it merely depends on pushing some button.

  • It's on news. "Scientists found largest prime number...". I'm not saying anything in news is important. I mean, to public it's a big deal. – Mohsen Jul 14 '13 at 23:38
  • It's quite a natural record to try and break, the fact it has been broken again is definitely of interest, though I think what @heinz is trying to say is that the numbers themselves aren't going to be particularly useful to anyone. Its just nice to test how far we can go. – Alex J Best Jul 14 '13 at 23:41
  • @Mohsen Why are scientists searching for them, isn't that mathematicians (or rather their computers') job, if anyones? – Christopher King Jul 15 '13 at 00:12
  • 4
    It's on news because it's math that grade school kids can understand, like digits of $\pi$. There is no value to more digits of $\pi$ either... – Thomas Andrews Jul 15 '13 at 00:36