Comment by echelon | Hacker News Reader

Comment by echelon | Hacker News Reader

Parent Full thread

I am not a mathematician or cryptographer, but here's my understanding (please, please correct me if I'm wrong)

Modern cryptography relies on the hardness of integer factorization. Things you want to hide are intractable to calculate on even the most powerful machines due to the underlying math not being workable in polynomial time (or similar low degree time). Age of the universe hard to brute force with our machines and known algorithms.

It has to do with the complex structure of the problem in our intuitive dimension. We haven't thought of any possible way to speed it up classically, and it's not apparent if there are such techniques.

The Riemann Hypothesis conjectures that there is a way to know the distribution of primes in a higher dimensional imaginary math. That the unintuitive and difficult system that gives us primes in real number space is somehow contained in a larger imaginary space, with some kind of regular structure, and that they are immediately accessible and calculable once you know the trick.

If the hypothesis is true, it's quite possible that NP hard problems are the same. That in some unintuitive higher dimension math we can solve the hardest problems in polynomial time.

NP-hard problems are also proven to be equivalent complexity, and if you figure out one then the rest are also solvable. If we figure out the trick behind it all (if such a thing exists), we might break everything. Or maybe we'll prove that there is no such free lunch.

I'm one of the ones hoping for computing to be easy. It would unlock so many possibilities. Fast math, in silico experiments, protein folding, etc. It unfortunately would also break all of the underpinnings of our industry, though. SSL, privacy, crypto, infosec, everything about the Internet...

Most people are betting that primes are hard, and it certainly does look that way.

> Modern cryptography relies on the hardness of integer factorization... P vs NP

This is not true for elliptic curve cryptography, or exactly true for RSA et al. ECC is based on the hardness of the elliptic discrete logarithm problem which is not exactly the same as solving integer factorization. However both can be tackled in polynomial time using Shor's algorithm [0], so both will be vulnerable once we have quantum computers. There are a handful of promising post quantum approaches, such as lattice cryptography. You don't need to solve P vs NP to break modern cryptography, you just need a computer that can run Shor.

[0] https://eprint.iacr.org/2017/598.pdf

"The Riemann Hypothesis conjectures that there is a way to know the distribution of primes in a higher dimensional imaginary math. That the unintuitive and difficult system that gives us primes in real number space is somehow contained in a larger imaginary space, with some kind of regular structure, and that they are immediately accessible and calculable once you know the trick."

RH does not imply this (under any reasonable interpretation of what you wrote; e.g. RH would not imply a fast algorithm that given n outputs the nth prime).

The prime number theorem says that the number of primes up to x (denoted pi(x)) is "well approximated" by Li(x). The Riemann hypothesis says that this is a REALLY good approximation. In particular, it says that the error incurred in approximating pi(x) by Li(x) is of size about sqrt(x). (More precisely sqrt(x)log(x).)

There is actually one interesting connection between RH and integer factorization. This has to do with the idea of "Mobius pseudorandomness." For simplicity, I'll phrase things in terms of not Mobius, but the Liouville function lambda.

The Liouville function comes up naturally if you are interested in whether the "typical" number has an even or odd number of prime factors. More precisely, define the function lambda(n) (the "Liouville function") as follows. lambda(n) = 1 if n has an even number of prime factors, and -1 if n has an odd number of prime factors. If you expected that about half of the positive integers have an even number of prime factors, then you would expect that lambda is 0 on average, i.e. that |(1/x) * sum_(n <= x) lambda(n)| tends to zero as x tends to infinity.

It turns out that this statement is equivalent to the prime number theorem. Further, it turns out that the Riemann Hypothesis is equivalent to the STRONGER statement that the size of the sums |sum_(n<=x) lambda(n)|, where lambda(n) is the "Liouville function," don't exceed size about sqrt(x). This is exactly what you would expect from the Central Limit Theorem if you thought that lambda(n) behaved like a Bernoulli random variable taking the values +1,-1.

What does this have to do with factorization? It's easy to compute lambda if you know how to factor n, so if computing lambda is certainly no harder than factoring. On the other hand, we don't know of any way to compute the Liouville function without factoring n. This isn't a proof that computing lambda(n) is at least as hard as factoring n, but it certainly seems to be the case.

Now, one rigorization of what it means for a sequence to behave randomly is that it doesn't correlate with any easily computable sequences. (Replace "easily computable" with "computable" and you are not too far from the definition of Martin-Lof randomness.) In particular, it shouldn't be easily computable.

So in other words, if you think that lambda behaves randomly, then it shouldn't be easily computable, which in turn means that factoring is hard!

But as mentioned above, one of the simplest consequences of lambda behaving randomly is (by the Central Limit Theorem) the Riemann hypothesis!

Hmmm? Is someone experimenting with GPT-3 commenting on NH? Because it sure feels like it - the comment is mostly grammatical, uses approximately correct jargon, and completely nonsensical.

Hello Ilya, if you're wondering why your comment isn't appreciated, it is because you are breaking the rules.

Please do not accuse people of being bots or shills, and if you have proof that someone is a bot (or an actual shill) then mail hn@ycombinator.com

Have a look at:

https://news.ycombinator.com/newsguidelines.html , the bot bit isn't explicitly mentioned but "Please don't post insinuations about astroturfing, shilling, brigading, foreign agents and the like." covers it nicely with the 'and the like' bit.

Thanks for clarification and pointing to the forum guidelines. I hoped I was being charitable, trying to explain away the cluelessness of the comment.

You're welcome.

The thing is HN has lots of people who do not have English as their first language and the bulk of these comments would be directed at people doing their level best to get it right. And being wrong in itself is a good basis for a correction rather than a put down. See the other comments to your parent comment for examples of how you could handle that with more grace.

i have no idea why this great comment got down voted.

Elliptic curve cryptography does not rely on the difficulty of prime factorization. That is likely why that comment you are replying to is downvoted; that comment doesn't answer the question that it is replying to.

For an intro to the math behind elliptic curve cryptography, here's a good read: https://hackernoon.com/what-is-the-math-behind-elliptic-curv...

this is new to me. i appreciate the response

Lazy trolling.

Reply on news.ycombinator.com