5
$\begingroup$

This question already has an answer here:

So I've read about the latest largest prime number discovery (M74207281), but I find it hand to understand what's the big deal because using Euclid's proof of the infinitude of primes we can generate primes as large as we want.

I'll be happy to know what I'm missing

$\endgroup$

marked as duplicate by Milo Brandt, Marc van Leeuwen, Pragabhava, Chris Godsil, Alex M. Jan 24 '16 at 17:50

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from mathoverflow.net Jan 24 '16 at 12:10

This question came from our site for professional mathematicians.

  • 1
    $\begingroup$ Theoretically, yes. On the practical side, Euclid does not tell you how to construct large primes. They have great practical value. $\endgroup$ – abatkai Jan 24 '16 at 11:59
  • 1
    $\begingroup$ Euclid's proof tell you how to construct new prime: In order to create new one, you multiple all the primes and add 1. $\endgroup$ – Alex L Jan 24 '16 at 12:04
  • 7
    $\begingroup$ $2*3*5*7*11*13+1 = 59 * 509$. $\endgroup$ – Oliver Braun Jan 24 '16 at 12:07
  • 2
    $\begingroup$ @AlexL It's not true actually. It's true that $p_1\cdots p_n+1$ is a prime if we assume $p_1,p_2,\dots,p_n$ are the only primes that exist. If you don't assume that the proof that it's prime breaks down. So since there are infinitely many primes you cannot assume $p_1\cdots p_n+1$ is always prime and in fact it usually isn't. $\endgroup$ – Gregory Grant Jan 24 '16 at 12:21
  • 1
    $\begingroup$ There is a BIG difference between FINDING big primenumbers and GENERATING big prime numbers, the former is (cu)cumbersome which is why it's a big deal, while the latter, cannot be done as prime numbers don't adhere to an exact sequence or the likes, known as of yet. $\endgroup$ – Zelos Malum Jan 24 '16 at 12:24
10
$\begingroup$

The short answer is: this isn't actually a big deal. It's a bit like finding another digit of $\pi$ - scientific journalists love writing articles about it, but it doesn't have that much significance.

That's not to say it's easy to generate the next largest prime. But the difficulties are all in the computer science, not the mathematics. The algorithm that falls out of Euclid's proof works like this: make a list $p_1, \ldots, p_n$ of all primes that you can, form $k = p_1 \cdot \ldots \cdot p_n + 1$, and compute the prime factorization of $k$. The prime factorization is guaranteed to contain a prime which wasn't on your original list.

However, this algorithm starts to become intractable computationally before too long: multiplying the known primes together, let alone factoring their product plus 1, starts to exceed the capabilities of modern computers long before you find primes which compete with the latest records.

A better idea is to look for really big numbers which you have reason to hope are prime and then try to check that they really are prime. A good collection of numbers to look at are the Mersenne numbers, i.e. numbers of the form $2^n - 1$. It's much easier to compute Mersenne numbers than it is to, say, multiply the first ten thousand prime numbers together, so you only have to test if the Mersenne numbers are prime. This is still really hard (the best primality testing algorithms are only so fast), but as computers get faster they can handle bigger numbers. Indeed, the reason the latest number is called $M74207281$ is that the number is:

$$2^{74207281} - 1$$

So there were no mathematical breakthroughs here - just getting more mileage out of a familiar algorithm. It's not clear to me that there were even any computer science breakthroughs; as far as I know they just use the same old primality testing algorithm on a faster computer. But there was something shiny and new for the journalists.

$\endgroup$
  • 5
    $\begingroup$ It is also worth mentioning that testing primality of Mersenne primes is faster than testing primality of generic number of that size. $\endgroup$ – Wojowu Jan 24 '16 at 12:56
4
$\begingroup$

It is true that the fact that a new largest known prime was identified is not much of a theoretical advance as it is well known there are infinitely many ones. And, theoretically there are even relatively simple procedures to find ever more primes.

However, one is so far out that doing it in practice is hard and if it succeeds it is thus of some news value. That being said, I think it is fair to say it is not something that leads to major excitement in the math community, since it is something that is expected to happen from time to time. Yet the process of searching still has some actual merit. I think the project GIMPS that found it does a good job at explaining it (from Announcement January 7, 2016):

While prime numbers are important for cryptography, this prime is too large to currently be of practical value. However, the search itself does have several practical benefits. Historically, searching for Mersenne primes has been used as a test for computer hardware. Earlier this month, GIMPS' prime95 software and members of a German computing community uncovered a flaw in Intel's latest Skylake CPUs. Prime95 has also discovered hardware problems in many individual's PCs.

Moreover, this newly found prime as most largest known primes is a Mersenne prime, that is a prime of the form $2^n -1$ and it is not known if there are infinitely many primes of this form. Now, it is expected there are infinitely many Mersenne primes, so this is also not that big a surprise, but still it is interesting.

$\endgroup$
  • 1
    $\begingroup$ As a remark: this answer outlines a heuristic on why we might expect infinitely many Mersenne primes. $\endgroup$ – Paul Plummer Jan 24 '16 at 16:10
2
$\begingroup$

As Euclid has proven there are infinitely many primes. But until now there is no simple (i.e. "polynomial") procedure that generates arbitrarily large primes at leisure.

The "prime records" we see now and then are very special primes, having a sophisticated number theoretic structure. Given such a record prime $p_*$ it would be computationally unfeasible nowadays to find the next larger prime.

$\endgroup$
  • $\begingroup$ What do you mean by "polynomial"? There are algorithms that are (or at least are assumed to be, which is the same for actually computing the primes) that are polynomial time algorithms to find the next prime or a prime of a given size. (I agree it is not feasible but not because it is not "polynomial".) $\endgroup$ – quid Jan 24 '16 at 14:01
  • $\begingroup$ @quid: I don't think so. See the status of Tao's polymath project no. 4 here: polymathprojects.org/category/finding-primes $\endgroup$ – Christian Blatter Jan 24 '16 at 14:06
  • $\begingroup$ I am aware of this. Please note my first parenthetical. $\endgroup$ – quid Jan 24 '16 at 14:09
  • $\begingroup$ @quid : The current best deterministic algorithms for finding a prime of size $k$ are $O(\mathrm{e}^{k/2+o(1)})$, which is not polynomial in $k$. An example of an $O(\exp(k/2))$ algorithm is starting with $10^k$ and testing successive odds for primality (and getting this fast estimate used RH up until the end of the '90s). If you have a deterministic polynomial time method then some fame and probably a little fortune await. $\endgroup$ – Eric Towers Jan 25 '16 at 4:12
  • $\begingroup$ @EricTowers we are talking sideways. The algorithm: On input $n$ test if $n$ is prime, if yes stop else test $n+1$ will (except well known conjectures are completely off) stop after something like $(\log n)^2$ iterations. And testing primes is polynomial, even proved to be so, too. Thus this algorithm will find a prime in something like $(\log n)^{8}$. Using your parametrization this would be $k^8$. Now it is true we do not know how to prove that it stops after $(\log n)^2$ iterations as our estimates for prime gaps are not good enough, but for practical problem this is irrelevant. $\endgroup$ – quid Jan 25 '16 at 10:56
2
$\begingroup$

TL;DR Euclid's proof guarantees that there will be a larger prime than the largest yet known, but does not appear to be a particularly efficient way of actually finding one.

As for why we would want to actually find a larger prime than any yet known: because it's there?


Reading one of the comments, I notice that you have heard of the Euclid-Mullin sequence, $$ a_n = \mathrm{lpf}\left(1+\prod_{k=1}^{n-1}a_k\right). $$

The right-hand side of this equation contains the famous formula from Euclid's proof of the infinitude of primes.

But it also applies the "$\mathrm{lpf}$" function to this formula, and there's the rub. That's the "least prime factor" function, and it not only requires you to factorize a very large number, it also requires you to determine whether the factors you have found are prime.

So the way to find a new world's largest prime using Euclid's proof would be as follows:

  1. Collect together all the known primes.

  2. Multiply all the known primes together (not a small task; some of these primes run into millions of digits).

  3. Add one.

  4. Test the resulting number from the previous step to determine whether it is prime.

  5. If the result of step 4 is that the number is prime, skip ahead to step 8. But very likely the number is not prime, and you must continue to step 6.

  6. Use the results of step 4 to write a factorization of the number from step 3. Insert those factors in a list of unique factors found in this step.

  7. Remove one number from the list in step 6, and return to step 4, using this number as the new input to step 4.

  8. Compare the prime number found in step 5 to the list of known primes that you last used in step 2. If your prime is larger than any of the previously-known primes, congratulations, you have found the new world's largest prime number! But it is very likely that your new prime will fit in one of the many huge gaps in the sequence of previously-discovered primes; in that case, add the new prime to the list of known primes, and then either return to step 7 (if there are still numbers in the list from step 6) or start the process over from step 2.

The reason this is so complicated is that Euclid's formula does not directly produce a new prime; rather, it gives you a number whose prime factors are guaranteed to be new. You still have to test the number for primality and (very likely) factorize it somehow in order to find one of these new primes.

Moreover, if you collected together all the $N$ known primes, they are not the first $N$ primes; there are enormous tracts of relatively "unexplored territory" between the end of the largest "first $M$ primes" table and the largest known Mersenne prime. So after some amount of primality-testing and factorization applied to the number you got from Euclid's formula, you may well find that all the new primes it produced fell into the gaps in the list of known primes. Eventually, if you reapply the formula often enough, you will find a new largest prime, but how many iterations will that take? It could take a very, very long time before you find any new primes that don't just fill in the huge gaps between the already-known ones.

In contrast, testing new candidates for a Mersenne prime has a low probability of success each time, but relatively efficient ways to confirm success when it occurs; and when it succeeds it is practically guaranteed to be a new world's record. (The only way it wouldn't be a new record is if some other computer was concurrently testing an even larger Mersenne prime.)

$\endgroup$
1
$\begingroup$

Not all numbers of the form $p\#\pm1$ are prime.

See Prime Pages, The Ten Largest Known Factorial/Primorial Primes

for a list of the largest known of these.

$\endgroup$
1
$\begingroup$

It's not true that $p_1\cdots p_n+1$ is always prime. It's true that $p_1\cdots p_n+1$ is a prime if we assume $p_1,p_2,\dots,p_n$ are the only primes that exist. BUT, if you don't assume that then the proof that it's prime breaks down. So since there are infinitely many primes you cannot assume $p_1\cdots p_n+1$ is always prime and in fact it usually isn't. And in fact
$2∗3∗5∗7∗11∗13+1=59∗509$ is an example (thanks Oliver Braun).

$\endgroup$
  • $\begingroup$ That is correct, but if we use Euclid–Mullin sequence, we can find prime number as large as we like $\endgroup$ – Alex L Jan 24 '16 at 12:24
  • $\begingroup$ @GeoffRobinson It's not strange, it's just the contradiction that is the basis of Euclid's proof of the infinitude of primes - which is (recall) a proof by contradiction. $\endgroup$ – Gregory Grant Jan 24 '16 at 12:26
  • $\begingroup$ @AlexL Sure in principle you can, but you can't in practice, because you have to factor a large number to find it. So that's no better than saying you can always find a prime as large as you want using Euclid's algorithm. Sure you can, but it might take longer than the life of the universe with today's compute power. $\endgroup$ – Gregory Grant Jan 24 '16 at 12:28
  • 1
    $\begingroup$ @AlexL The point is not that there's a prime that big but that we could actually find it. Because using the simple minded algorithms we could never find one that big. You can only get your hands on one that big if you do something clever - like search for Mersenne primes. $\endgroup$ – Gregory Grant Jan 24 '16 at 12:30
  • 1
    $\begingroup$ @AlexL Basically yes, Euclid Mullin only defines a sequence theoretically but it doesn't give you an efficient way to actually write down the terms of the sequence. While Mersenne gives you a specific very efficient algorithm for determining whether some types of integers are prime. Using any other known algorithm for finding primes it would have taken an astronomical amount of time to find a prime that large. That's the reason it's news. Keep in mind that even though Mersenne is efficient, most numbers of that form are not prime so it can still take years to find one. $\endgroup$ – Gregory Grant Jan 24 '16 at 12:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.