5 ms·
Mathematicians Make a Major Discovery About Prime Numbers
- paul_f 12y agoThis was a bit of a let down. I didn't see anything "major" about this at all.
- tempodox 12y agoConsequently, what is “major” about this is the gap in your understanding.
- logn 12y agoThe original discovery this recent news pertains to: https://news.ycombinator.com/item?id=6784383 https://news.ycombinator.com/item?id=6784383 , https://news.ycombinator.com/item?id=6766097 https://news.ycombinator.com/item?id=6766097
- logicallee 12y agoYes, it's been a relatively prime year for number theory.
- sgt101 12y agoWhat, we wonder will 2017 bring?
- raverbashing 12y agoPun intended? Edit: http://en.wikipedia.org/wiki/Relative_prime http://en.wikipedia.org/wiki/Relative_prime
- xkarga00 12y agoThis is very interesting. Also Primecoin seems to be helpful in the prime numbers field. http://primecoin.io/ http://primecoin.io/ https://en.wikipedia.org/wiki/Primecoin https://en.wikipedia.org/wiki/Primecoin https://en.wikipedia.org/wiki/Cunningham_chain https://en.wikipedia.org/wiki/Cunningham_chain https://en.wikipedia.org/wiki/Bi-twin_chain https://en.wikipedia.org/wiki/Bi-twin_chain
- raverbashing 12y agoLooks like it's a better proof of work than a meaningless hash. I'm more sympathetic to using big amount of calculation to actually doing something useful, like calculating prime sequences. I wonder what other kind of (useful) work could be used as payloads for virtual currencies
- imaginenore 12y agoLarge primes are pretty useless. Everyday crypto generally uses 512-bit primes, which can be generated very easily and quickly on the fly.
- lukeschlather 12y agoThis website uses a 2048-bit key. 512-bit RSA keys are considered generally insecure and easy to crack. 2048 is the industry standard. Your point is probably still valid, but we don't know how high we can go.
- raverbashing 12y agoIt's not about finding a large prime, it's finding prime densities, gaps, sequences, etc
- wolfgke 12y ago512 bit primes lead to an RSA key length of 1024 bits, since the key length is the length of the product of two primes.
- czzarr 12y agoIt's meaningless for a reason. https://download.wpsoftware.net/bitcoin/asic-faq.pdf https://download.wpsoftware.net/bitcoin/asic-faq.pdf
- Forbo 12y agoGridcoin uses the Berkeley Open Infrastructure for Network Computing as a way of obtaining useful work for cryptocurrency. http://www.gridcoin.us/ http://www.gridcoin.us/ Edit: This is perfectly relevant to topic of discussion and informative. BOINC is a completely valid platform for distributed computing for many different areas of research including mathematics, medicine, molecular biology, climatology, environmental science, and astrophysics.
- porter 12y agoWhat are the implications of this?
- hyperliner 12y agoOne 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 agoHonestly, 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.)
- kbwt 12y agoThe article is a repost from https://www.quantamagazine.org/20141210-prime-gap-grows-after-decades-long-lull/ https://www.quantamagazine.org/20141210-prime-gap-grows-afte...
- sctb 12y agoWhich was discussed here: https://news.ycombinator.com/item?id=8731040 https://news.ycombinator.com/item?id=8731040
- Bud 12y agoSo great that Tao turns out to be a protege of Paul Erdõs.
- Bahamut 12y agoI took an analytic number theory course with one of the authors of one of papers, Kevin Ford, while a grad student at UIUC - he was hard on me as a student from what I remember. Tao's comment on prime number problems are spot on - the study of prime numbers is perhaps the most raw and magical of all the areas of mathematics. Intuition usually gives very simple "guesses" (most mathematicians have superb intuition) on basic properties, but proving them often proves to be elusive, which is why it taunts mathematicians.
- thomasahle 12y agoTerry's own announcement of the new top result: http://terrytao.wordpress.com/2014/12/16/long-gaps-between-primes/ http://terrytao.wordpress.com/2014/12/16/long-gaps-between-p... The new bound cuts one of the logloglog factors from the denominator. At least that makes the formula slightly neater :)
- Nmachine 12y agoHey wired, can you not recount the entire history of whichever field the story you are covering is a part of in every article? Also, when I hit the back button I expect to go back.
- sj4nz 12y agoWired is not a mathematics journal, so probably not. "Know your audience." That's perfectly fine for a "general audience" medium. But a broken Back button? Yeah, they should fix that.
- UhUhUhUh 12y agoJust curious: has there been anything on patterns in primes? There are so many constraints that I even wonder how there could not be patterns in the distribution.
- dzhiurgis 12y agoPrime is the pattern?
- justifier 12y agodepends on your definition of patterns.. Eratosthenes sieve is a pattern of sorts, but one with many dependent variables that we are unsure how to make agnostic from the pattern back to its initial state.. essentially we are unable to find the nth prime number, but if we already ran the pattern up to the nth prime number, finding n+1 is possible with enough effort . mersenne primes are primes that all share the form of 2^p-1 and they appear all through out the momentum of prime numbers, but again, our problem is finding when the next one will occur and our best solutions boil down to rote testing.. . one person involved in the discovery here reported has a theorem named after a colleague and himself that is more along a traditional pattern, they call it an arithmetic progression, here is one such example.. 6,171,054,912,832,631 + 366,384 · 223,092,870 · n, for n = 0 to 24 each of the 24 numbers in that sequence will be prime . i came across this momentum sometime last week: n**2-n+41 the first 40 values for n, 1..41, will produce primes.. after that the distribution of primes for whole values of n becomes erratic.. why? unsure and investigation quickly proved a difficult avenue of research so i let that distraction lie for another day (i) http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes (ii) http://en.wikipedia.org/wiki/Mersenne_prime http://en.wikipedia.org/wiki/Mersenne_prime (iii) http://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem http://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem
- joyofdata 12y agoThere is Ulam's Sprial for example. http://en.wikipedia.org/wiki/Ulam_spiral http://en.wikipedia.org/wiki/Ulam_spiral
- euid 12y agoFor those who don't wish to read all the news fluff to hear about a mathematical discovery:[1] Abstract. We show that there exists pairs of consecutive primes less than x whose difference is larger than t(1+o(1))(log x)(log log x)(log log log log x)(log log log x)⁻² for any fixed t. This answers a well-known question of Erdős. Their "key proposition", as stated, is:[2] Proposition 5. Fix δ > 0. Let m < Uz⁻¹(log₂ x)⁻² be even and let Iₘ ⊆ [x/2, x] be an interval of at least δ|ℝₘ| log x. Then for x > x₀ (δ, C_U) there exists a choice of residue classes aₙ (mod n) for each prime n ∈ Iₘ such that p ∈ ℝₘ ⇒ p ≡ aₙ (mod n) for some prime n ∈ Iₘ. [1]: Here is the paper linked: http://arxiv.org/pdf/1408.5110v1.pdf http://arxiv.org/pdf/1408.5110v1.pdf (strangely, while the news article mentions two papers, both links go to the same one in both the original and Wired articles ...). [2]: I changed all instances of q to n in this so that I could type most of the subscripts, but any errors are mine.