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: 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.