4 ms·

One implication straight from the article (I am a mere mortal, unlike you who asked the question): The new work has no immediate applications, although underst

One implication straight from the article (I am a mere mortal, unlike you who asked the question): The new work has no immediate applications, although understanding large prime gaps could ultimately have implications for cryptography algorithms. If there turn out to be longer prime-free stretches of numbers than even Cramér’s conjecture predicts, that could, in principle, spell trouble for cryptography algorithms that depend on finding large prime numbers, Maynard said. “If they got unlucky and started testing for primes at the beginning of a huge gap, the algorithm would take a very long time to run.”

m_eiman 12y ago
“If they got unlucky and started testing for primes at the beginning of a huge gap, the algorithm would take a very long time to run.” Wouldn't it also mean that the first prime after such gaps will be selected more often, assuming a random starting point for prime searches? That might be a bigger problem than having to wait longer for the selection to finish.
- jerf 12y ago
  Honestly, I wouldn't worry about either problem. The degree of "unlucky" required here is almost certainly below the noise threshold. Otherwise we would have noticed by now, because prime-based crypto is, after all, not a theoretical thing, but something extremely-widely deployed in the field, and in practice, we do not observe this problem. Since we do not observe this problem, we therefore are not observing this problem; QED. (The "noise threshold" is provided by the fact that processors are not in fact 100% accurate, but do indeed have a low-but-non-zero error rate. When the probability of a randomized algorithm failing drops below the probability that the processor literally got the computation wrong, it ceases to matter in practice. And one could argue it ceases to matter even before that, but it certainly ceases to matter at that point. Hence I call it the "noise floor". It's so low we are used to just assuming it is zero, but in fact it is not.)
  - bdamm 12y ago
    This is the kind of work that the NSA, had they known it decades ago, would have kept to themselves. They certainly have no shortage of mathematical talent working on the problem.

m_eiman 12y ago

“If they got unlucky and started testing for primes at the beginning of a huge gap, the algorithm would take a very long time to run.” Wouldn't it also mean that the first prime after such gaps will be selected more often, assuming a random starting point for prime searches? That might be a bigger problem than having to wait longer for the selection to finish.

jerf 12y ago
Honestly, I wouldn't worry about either problem. The degree of "unlucky" required here is almost certainly below the noise threshold. Otherwise we would have noticed by now, because prime-based crypto is, after all, not a theoretical thing, but something extremely-widely deployed in the field, and in practice, we do not observe this problem. Since we do not observe this problem, we therefore are not observing this problem; QED. (The "noise threshold" is provided by the fact that processors are not in fact 100% accurate, but do indeed have a low-but-non-zero error rate. When the probability of a randomized algorithm failing drops below the probability that the processor literally got the computation wrong, it ceases to matter in practice. And one could argue it ceases to matter even before that, but it certainly ceases to matter at that point. Hence I call it the "noise floor". It's so low we are used to just assuming it is zero, but in fact it is not.)
- bdamm 12y ago
  This is the kind of work that the NSA, had they known it decades ago, would have kept to themselves. They certainly have no shortage of mathematical talent working on the problem.