SoylentNews is people
SoylentNews
One of the most important unsolved problems in mathematics may have been solved, retired mathematician Michael Atiyah is set to claim on Monday. In a talk at the Heidelberg Laureate Forum in Germany, Atiyah will present what he refers to as a "simple proof" of the Riemann hypothesis, a problem which has eluded mathematicians for almost 160 years.
Born in 1929, Atiyah is one of the UK's most eminent mathematical figures, having received the two awards often referred to as the Nobel prizes of mathematics, the Fields medal and the Abel Prize. He also, at various times, served as president of the London Mathematical Society, the Royal Society and the Royal Society of Edinburgh.
If a solution to the Riemann hypothesis is confirmed, it would be big news. Among other things, the hypothesis is intimately connected to the distribution of prime numbers, those indivisible by any whole number other than themselves and one. If the hypothesis is proven to be correct, mathematicians would be armed with a map to the location of all such prime numbers, a breakthrough with far-reaching repercussions in the field.
[ALSO COVERED BY]:
Sir Atiyah's conference on the Riemann Hypothesis
Michael Atiyah and the Reimann hypothesis
[RELATED]:
(Score: 5, Informative) by BsAtHome on Saturday September 22 2018, @11:20AM (10 children)
It would reduce the search space for finding primes. That is a problem because the premise of PKI is that the search space is too large to traverse in reasonable time. If you have a map, then it becomes possible to find the key(s) in reasonable time and your security is gone.
(Score: 4, Insightful) by theluggage on Saturday September 22 2018, @12:39PM (7 children)
...however, Its safe to assume that any brute-force PK crackers out there have been using Riemann to optimise their searches for years: even a good "rule-of-thumb" would work for that purpose - vastly speeding up the search at the expense of a tiny probability of getting it wrong (which would give you the consolation prize of disproving Riemann).
Any hypothesis that has survived the scrutiny of mathematicians for years - all it takes is one counter-example or the discovery of one line of faulty reasoning and its gone - is highly unlikely to be false and, if it is, any inaccuracies are likely to be subtle. That's not, for one moment, diminishing the significance of a proof to pure mathematics (and who knows what new insights will spring from that proof) but its not going to have any overnight significance for practical applications.
(Score: 1, Insightful) by Anonymous Coward on Saturday September 22 2018, @05:34PM (4 children)
No, that's not the way it works. A failure to find a prime if you assume Riemann is real would disprove the theorem, but there has to be a prime within that range anyway for other reasons (prime number theorem and Cramér's conjecture, among other things), so you'll never get a counter-example. What it does do is tell you is how many primes there are in a range and roughly where they are and a huge chunk of where they aren't (which increases as you find more primes in a range). The problem is that Reimann's hypothesis cannot be assumed true for brute forcing because if it isn't true, then you miss options.
Here is an analogy, say that health officials want to find all the people in a specific community that are radioactive. To do a brute force search, you have to literally search every person to see if they are radioactive. Now, say that you've notice that it seems that radioactive people live on average a certain distance apart and seem to have a certain maximum distance between them. Yeah, that is helpful, but not very helpful because you still have to check everywhere in case you missed someone. On the other hand, if you know, for a fact due to the nature of reality, that radioactive people HAVE TO be a certain maximum distance apart, they have a specific distribution, AND how many radioactive people live in certain neighborhoods, that drastically drops your search efforts because you only have to check the maximum distance around each person you find, where to start looking, AND you know when you found them all in a given area, because there cannot be any more by definition.
(Score: 3, Insightful) by theluggage on Saturday September 22 2018, @07:16PM (3 children)
So finding 10 primes in a range where Riemann said there would be 9, or exhaustively checking that range and only finding 8 would be a counter-example (that doesn't mean that it would be productive to go looking, but does suggest that there are no 'trivial' exceptions). If not, the alternative is that even if Riemann were true it would still only be a "rule of thumb" when it came to hunting for primes.
If you're brute-forcing for practical reasons (e.g. breaking encryption) then a massive reduction in the search space is worth a small risk that you might miss a few options. NB: gp/ggp post was talking about the implications for the security of prime-number-based encryption, not the sheer mathematical joy of finding all the primes.
Except, in your radiation scare example, checking everybody might take a year, by which time many of those contaminated would have developed fatal tumours. Prioritising the areas you search based on an "educated guess" might let you find and save 90% of the affected within a month - and doesn't preclude you going on to complete the year-long search.
The consequences of "missing" a few candidates in a search for a cryptographic crack is even less serious if it means that you get good odds of getting a result before the heat death of the universe.
(Score: 1, Informative) by Anonymous Coward on Saturday September 22 2018, @07:50PM (2 children)
I don't see your point, Reimann is more than a rule of thumb. It literally tells you how many primes there are and each one found provides information on the ones left. If you have a large collection of primes, say you are the NSA slurping them up and bruting them, it will tell you how many you have left and where to look. For example, if you use the theorem and it tells you that where you are looking there are 10, then if the theorem is true, there are 10 PERIOD. You find all ten, you are done; take your ball and go home. If you get lucky, and they are the first 10 numbers you check, those are the only numbers you need to check. That is drastically different then the state of affairs right now, because you cannot know in advance exactly how many there are, only a rough guess based on probability distributions.
Additionally, Reimann being true means that there are areas that you can say, for a fact in advance, there are no primes. You can completely exclude those areas from your search and not worry about missing any. Without Reimann being true, the best you can do is use a non-related conjecture to assign a non-zero probability to the region and whether or not a previous number was prime doesn't affect those probabilities.
And, if you want to be deep down practical, it wouldn't affect your private key at all, because the current recommendation is to use ECC, as they don't depend on keeping prime numbers secret.
(Score: 2) by theluggage on Saturday September 22 2018, @11:53PM (1 child)
That actually was my point, in response to the G.P. arguing that you couldn't find a counter-example: if Riemann makes a falsifiable prediction (like there are "10 primes in this range") then potentially it could be disproved by counter-example (e.g. finding 11 primes in the range). If it couldn't make a falsifiable prediction (i.e. it only said where a prime is likely to be) then it would be no more then a rule of thumb that couldn't guarantee success - which would have made the rest of the discussion moot.
You can already exclude those areas from your search by simply assuming that Riemann is true on the basis that its been around since the 19th century and nobody has managed to disprove it. An algorithm that will almost certainly crack a key in a week is better than an algorithm that is guaranteed to crack it in a year (or whatever the relative time spans are).
No, if you want to be deep down practical you realise that it could be years before everybody adopts the current recommendation and you usually don't have any control over what encryption other people use. (God, if only other people even knew how to generate a key and paste the public part into an email or web form...)
(Score: 2) by DrkShadow on Sunday September 23 2018, @01:47AM
Unsure if it's been said, but per the original comment's question.. the reason that having a proof of Reimann's hypothesis is that now you can be sure you fully covered a given area. If you _assumed_ it, but it was taking an awful long time to search for the solution while skipping chunks per Reimann, you can't be sure that you covered all the possible primes in an area -- whereas with a proof, you can be sure, even without checking every last number.
(Score: 3, Interesting) by FatPhil on Sunday September 23 2018, @01:28AM (1 child)
Truthiness of *RH does not affect crypto in any way, shape, or form. Some computational bounds when it comes to *proof* of primality are defined contingent on *RH, but the reality is that you don't need *proof* of primality, you just need a number that seems to behave like a prime, and these bounds are irrelevant once P(you're wrong about a number's primality) < P(attacker can guess your factors). That, and you can use Maurer's method to generate easily-provable primes, if you really care about proof, which you shouldn't. Or just not use a M-R test for the proof stage - maybe ECPP or APRCL instead, depending on the sizes involved.
The amount of wrongthink in this subthread is quite painful to read. I'm not picking on you, the people you're responding too are just as wrong in other ways. For more info, just read C&P PN:ACP.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by theluggage on Sunday September 23 2018, @02:28PM
My comments were based on assertions made by other posters (I did try to make liberal use of conditional phrases like "If Riemann predicts such-and-such then...").
What I was really challenging was the proposition that (Hypothesis X) could be used to greatly optimise a real-world application but only after it had been mathematically proven... despite (X) having survived so much scrutiny that the risk of it being false was tiny c.f. the benefits of assuming its truth. That's not really a mathematical issue and doesn't depend on the details of (X).
Of course, if, as you're claiming, RH has no significant application to crypto then, well, garbage in - garbage out :-) - but whether or not other posters' assertions about the mathematics of RH were true, their application those assertions it to the real world was flawed. Proof of RH would be of huge mathematical significance, but even if RH were useful for crypto, it would already have been useful for crypto for years.
There's a sort of argument that occurs when A is challenging the assumptions made by B in applying a mathematical principle to a practical problem, but B responds as if A were attacking the mathematics itself...
(Score: 3, Informative) by ants_in_pants on Sunday September 23 2018, @12:57AM (1 child)
the fastest known probabalistic primality test(which is what's relevant here) is very likely correct independent of RH. I think it becomes always correct if RH, but I don't know the details.
Faster primality testing wouldn't make it easier to factor 2-large-prime-factor numbers. Primality testing takes the same asymptotic time even if you know every single prime number.
-Love, ants_in_pants
(Score: 2) by ants_in_pants on Sunday September 23 2018, @01:00AM
Factorization, not primes, in that last sentence there. Sorry.
-Love, ants_in_pants