6 ms·
Sudden Progress on Prime Number Problem Has Mathematicians Buzzing
- Xeoncross 13y agoDoes this mean as much as I think it does? Aren't most of our current cryptography schemes based on prime numbers taking time to calculate?
- lutusp 13y agoThe fact that mathematicians have refined the theoretical distance between pairs of primes has precisely no effect on the difficulty of factoring large composites. Those are completely unrelated problems.
- fiatmoney 13y agoI would imagine that proving they are completely unrelated would be a significant result in and of itself.
- mden 13y agoI think this is a completely fair point. Things in mathematics are astoundingly interconnected and you never know whether a seemingly benign proof will turn out to be the key to unlocking something much more pivotal.
- lutusp 13y agoProving the absence of something lies in the nether regions of science and mathematics. Consider the problem of proving the absence of Bigfoot -- it can't be done. This is a well-understood logical problem with a storied past: http://en.wikipedia.org/wiki/Russell's_teapot http://en.wikipedia.org/wiki/Russell's_teapot
- wglb 13y agoNo. If someone discovers a shortcut in factoring very large numbers, then it will have the attention of cryptographers.
- csense 13y agoNo. Finding random primes is easy, especially if you don't mind using methods which allow an extremely tiny probability of error [1] -- this is standard practice in cryptography. Finding random big primes p and q is easy. Multiplying them together into a product r = pq is easy. RSA cryptosystem picks p and q when generating the key, multiplies them, then throws away original p and q values. Only r is stored in the key. Cracking the RSA algorithm itself [2] is basically equivalent to turning r back into p and q. RSA is based on the hardness of factoring an integer into a product of primes. I don't think this conjecture will lead to practical improvements in cryptography / cryptanalysis, at least not with respect to cryptosystems that are currently widely used. [1] http://en.wikipedia.org/wiki/Primality_testing#Probabilistic_tests http://en.wikipedia.org/wiki/Primality_testing#Probabilistic... [2] Of course, there are many more attack vectors on specific implementations of the RSA algorithm, like trying to gain information on the secret key by measuring time taken to encrypt a message, measuring heat/power consumption/electronic noise, taking advantage of implementations that use a poor source of randomness, hacking into the system where the private key is stored, or bribing/threatening a human with legitimate access to the private key (as covered in http://xkcd.com/538/ http://xkcd.com/538/).
- nitrogen 13y agoYou run into problems, though, if you randomly select one of the same prime factors as someone else: https://www.hnsearch.com/search#request/all&q=gcd+public+key https://www.hnsearch.com/search#request/all&q=gcd+public+key
- gizmo686 13y ago> Cracking the RSA algorithm itself is basically equivalent to turning r back into p and q. This has not been proven. RSA encrypts by taking C=m^e (MOD N). The normal way of decrypting is to take C^d (MOD N), where d can be efficiently computed if you know the factors of N. However, all you need to do to decrypt C is to take the e`th root (mod n). It has not been shown that the ability to do so allows you to factor N. In fact, it appears (after a few minutes of research, so someone please correct me if I'm wrong), that their is evidence that breaking RSA is easier than factoring [1] [1]http://crypto.stanford.edu/~dabo/pubs/papers/no_rsa_red.pdf http://crypto.stanford.edu/~dabo/pubs/papers/no_rsa_red.pdf
- has2k1 13y agoWhat it means is that, although on the whole consecutive prime numbers tend to have larger separations as the magnitude increases, you will still be able to find consecutive primes with smaller separation sizes. The current proof puts that limit at 600. The twin prime conjecture posits that the limit is 2, i.e you can never exhaust pairs of consecutive primes with the smallest possible separation size.
- mistercow 13y agoSome of our current cryptography schemes are based on it taking time to factor large numbers, but this is not the same thing as finding prime numbers. The basic principle is that if I take two large prime numbers, P1 and P2, and give you their product, Q, then it will take you a very long time to learn P1 and P2 unless I give you one of them. It is actually very important that the hardness of that problem does not come from the difficulty of finding prime numbers. Which numbers are prime is a question that is independent of breaking any particular key, which means that if that were the source of hardness, you could reuse the work from breaking one key to break future keys, by storing a list of the prime numbers you calculated. This would be a Bad Thing. There are a lot of misconceptions, in fact, about hardness, prime numbers, and factorization. People often assume that primality testing and factorization are equivalent, and that both are NP complete. In fact, PRIMES is known to be in P, and (the decision version of) integer factorization is probably not NP complete (it is in NP by way of PRIMES being in P), although it is not known if it is in P.
- chrisfarms 13y ago> There are a lot of chances in your career, but the important thing is to keep thinking I hope this quote gets picked up and cited throughout future history
- leeoniya 13y agoreminds me of the Feynman Algorithm [1]: 1. Write down the problem. 2. Think real hard. 3. Write down the solution. [1] http://c2.com/cgi/wiki?FeynmanAlgorithm http://c2.com/cgi/wiki?FeynmanAlgorithm
- justinpombrio 13y agoIt's very easy to forget the first step :-)
- RBerenguel 13y agoAnd the second...
- DrewRWx 13y agoAnd the third can be a real strain on the wrist.
- RBerenguel 13y agoYes, and rewriting is the real pain, actually.
- vanderZwan 13y agoThat's actually the tricky bit, because often you're just thinking really hard that you're thinking really hard about the problem.
- RBerenguel 13y agoOr thinking about the wrong attack, and giving up. Or just thinking hard about how to define something... Or... Research is hard.
- taspeotis 13y agoPrevious discussion here: https://news.ycombinator.com/item?id=6766097 https://news.ycombinator.com/item?id=6766097
- z92 13y agoPrevious discussion here 272 points, 93 comments, 3 days ago.
- abuehrle 13y agoI'm confused by the "Admissible Combs" sidebar. Can someone help me understand? "Roughly speaking, a comb is admissible if there is no obvious reason why its teeth couldn’t point entirely to primes infinitely often as you move it along the number line" Then: "A much more audacious conjecture called the prime k-tuple conjecture ... posits that any admissible comb will point entirely to primes infinitely often." Isn't this just saying the prime-tuple conjecture states that admissible combs are admissible?
- justinpombrio 13y agoAdmissibility doesn't say that a comb's teeth will point entirely to primes infinitely often, it merely says (as you quoted) that there's no obvious reason its teeth won't point entirely to primes infinitely often. I suspect that "obvious reason" is being used as shorthand for some technical definition the article doesn't try to state. Any mathematician here that knows more?
- impendia 13y agoSure. {n, n + 2, n + 4} is a 3-tuple that is not admissible: One of n, n + 2, and n + 4 will always be divisible by three, so the tuple has no chance to ever represent three prime numbers for one value of n. (Except for n = 3.) Conversely, {n, n + 2, n + 6} is an admissible 3-tuple. There's no fixed integer that will always divide at least one of n, n + 2, and n + 6, so we believe that there are infinitely many n for which n, n + 2, and n + 6 are all prime.
- justinpombrio 13y agoAnd so the claim is that there is no less obvious reason that a comb might not be all primes only finitely often. That is an audacious claim :-).
- hawkharris 13y agoWhen I ordered a set of three foot-long chicken parmesan sandwiches from Subway a few weeks ago, the guy behind the counter said, "Because prime numbers are fundamentally connected with multiplication, understanding their additive properties can be tricky." I was confused at the time, but it makes sense now.
- deleted 13y ago[deleted]
- coldcode 13y agoSince counting numbers are so regular I've always wondered why finding primes is so hard. Then again I have no hair so using combs is a mystery.
- jostmey 13y agoNot being able to understand the intricacies of this proof, I can take away but one message. Genius can come from anywhere, even from an academic who was only able to find a job working at a Subway diner. So be open to good ideas - they can come from anybody, anywhere.
- jostmey 13y agoAnd to top it all off, this Mathematician was in his late fifties when he published his breakthrough proof!
- eps 13y agoIt's not the age, it's the marital status that affects the productivity the most.
- tomrod 13y agoI find myself downright inspired as a family man.
- pallandt 13y agoWere you being sarcastic? I've heard this before and it's usually considered that once someone gets married/has a family of their own, they simply will have to devote much less time to their profession/'hobbies' (like math) because of time constraints, and then they just start degrading due to lack of practice etc. One of the times it was specifically brought up in reference to a known mathematician. The takeaway being that getting in a relationship, or even married, automatically disqualifies you from achieving anything of great importance in the future....made me pretty sad that it's such a common pattern of thought.
- tomrod 13y agoI'm not being sarcastic. Marriage and family gave me reason and impetus to get my crap together and focus. I am easily distracted by sophomoric pursuits--now I choose hobbies and what not that I can share with the kids. One we really enjoy is kite building. But then, I started my family early. I didn't have much of an established pattern of productivity before. So my baseline comparison may be way off.
- charlieflowers 13y agoAre they still at 600?
- enum 13y agoThis abstract suggests that the bound may be lower: http://jointmathematicsmeetings.org/amsmtgs/2160_abstracts/1096-11-441.pdf http://jointmathematicsmeetings.org/amsmtgs/2160_abstracts/1... From http://jointmathematicsmeetings.org/meetings/national/jmm2014/2160_program_ss23.html http://jointmathematicsmeetings.org/meetings/national/jmm201...
- charlieflowers 13y agoHoly cow. You could almost say (naively I suppose), "They're almost there!" Of course, who knows if the distance between 600 and 12 is infinitely easier than the distance between 12 and 11. Still ... Progress!
- Zitrax 13y agoAlso from the article: "Conceivably, Maynard said, someone with a clever sieve idea could push this limit as low as 6. But it’s unlikely, he said, that anyone could use these ideas to get all the way down to a prime gap of 2 to prove the twin primes conjecture." So seems like something completely different is needed to actually prove the twin primes conjecture.
- fhars 13y agoNo. That abstract says that the bound it 12 if the Elliot-Halberstam conjecture holds. Under that assumption, the bound has been 16 since 2000. The trick that brings the number down from 16 to 12 under that assumption is the same that brings the proven number down to 600. This is actually described in the linked wired article.
- charlieflowers 13y agoAh. Thanks for the clarification.
- Houshalter 13y agoRelated questions, what are the open problems with prime numbers? Not that I'd ever solve them, but I was having fun using machine learning algorithms try to predict the next prime number in a sequence and it was kind of interesting.
- wolfgke 13y ago- Goldbach's conjecture (http://en.wikipedia.org/wiki/Goldbach%27s_conjecture http://en.wikipedia.org/wiki/Goldbach%27s_conjecture) - Goldbach's weak conjecture (http://en.wikipedia.org/wiki/Goldbach%27s_weak_conjecture http://en.wikipedia.org/wiki/Goldbach%27s_weak_conjecture) - Harald Helfgott claims that he proved it - Is factoring in P? (it is known that prime testing is in P; thus the factoring is in NP ∪ coNP) - if it were true, RSA would be broken immediately (and some expert that I talked to told me, he believes that such a factoring algorithm could probably be extended to break ECC, too) - Riemann hypothesis (http://en.wikipedia.org/wiki/Riemann_hypothesis http://en.wikipedia.org/wiki/Riemann_hypothesis) - Do for each even number n exist two prime numbers p > q such that n = p-q?
- throwaway1979 13y agoTwo points: - In math, an innovative "attack" (such as a technique to approach a problem) can result in years of subsequent research that progresses a field. Zhang deserves a lot of credit for his accomplishment! - He shouldn't have had to work at subway. If only our society held intelligent people in the same regard as athletes. What we have right now (hoops to get tenure, publish or perish culture, etc.) is a joke. I review papers for some notable conferences in my subfield in CS. This week I read about a dozen papers. The ones that pained me the most were written by very smart people solving made up and artificial problems. But hey ... you need to publish this crap to graduate/get tenure/get next grant/whatever. How about a basic income for everybody with a PhD?
- JayNYC 13y ago"How about a basic income for everybody with a PhD?" How about a basic income for everybody? I am always amazed, how unsuccessful PhDs in life are. Myself included.
- charlieflowers 13y agoWhy? Existential crisis?
- dsr_ 13y agoA doctorate in most fields is proof of a degree of general smartness and an ability to work rigorously in the field. It doesn't necessarily have anything to do with good judgement, luck, diplomacy, social skills, practical skills, or any of the thousand other things that contribute to success in life.
- jl6 13y agoTo do a PhD you have to be smart enough to be able to do one, and dumb enough to actually do one.
- 13y ago
- dmak 13y agoCould someone explain this in layman's terms? What does it mean to have infinitely many pairs of primes separated by 600?
- lutusp 13y agoIf the original claim is true, it means that the maximum numerical separation between primes is 600, meaning primes may sometimes be separated by a smaller gap, but no two primes will be separated by a larger gap, a numerical distance greater than 600. What this means is, if there are no gaps between primes a and b greater than 600 (i.e. |a-b| > 600), if all prime pairs have a smaller gap, then given the size of the set under consideration, it follows that there are an infinite number of pairings {a,b} in which their separation is 600 or less (|a-b| <= 600). Also, in mathematics, finding an example of a property isn't very difficult. The difficulty lies in proving a theorem that makes a universal statement about that property -- that's the real challenge. If that answer wasn't clear, don't hesitate to ask a clearer question.
- ipince 13y agoI don't think this is right. There are certainly prime gaps that exceed 600. In fact, the higher you up (in the number line), the higher these prime gaps tend to get. http://en.wikipedia.org/wiki/Prime_gap http://en.wikipedia.org/wiki/Prime_gap What's being said here is that despite of that, there will always be prime gaps smaller than 600. No matter how high you go, you can always find a pair of primes that are separated by less than 600. In other words, pick the biggest N you can ever dream of, and there will exist primes p1 and p2 such that they are both bigger than N and their difference is smaller than 600.
- lutusp 13y agoYes, you're right, and it's too late for me to either delete or edit my original post. :( In light of that, I think the discussion and work revolves around discovering the smallest gap as the numbers themselves become larger and tend toward infinity. Obviously the very smallest prime gap is that between 2 and 3, i.e. 1, and there are a great number of primes separated by 2, and the Twin Prime Conjecture asserts that there will always be occasional pairs of primes separated by 2 no matter how large the numbers themselves become. The present work is in part meant to put that conjecture on a more analytical footing. I would love to delete my original post.
- danielharan 13y agoWhat I find surprising is that there's an online tool for math collaboration (github for maths?), and that it turns out to be rather useful.
- fractalsea 13y agoCurrent list of attempts: http://michaelnielsen.org/polymath1/index.php?title=Bounded_gaps_between_primes http://michaelnielsen.org/polymath1/index.php?title=Bounded_...