Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Is there a real world outcome to this result?


There are many, many, many consequences for prime numbers--which to me are concrete enough to be interesting (and are way more concrete than what 99% of mathematicians work on!).

On the other hand, I doubt this proof will help you to build a faster gizmo or something in the real world.. especially since it's proving something we really think is true (a consequence of the Generalized Riemann Hypothesis), and for real-world applications you can just assume the thing that we think is true is actually true (even if we haven't been able to prove it for a century). (E.g., you don't need to prove that factoring is hard to use cryptography for practical purposes..)


I think it's fair to say that this could lead to certain new things becoming known about the distribution of primes. This could have implications for cryptographic algorithms that depend on prime numbers being hard to find.


Careful, prime numbers are not hard to find.

Like, try

  openssl prime -generate -bits 2048
Congratulations, you just found a prime that is big enough for every cryptographic protocol that uses prime numbers (not counting unusual and non-deployed post-quantum proposals).

Some number theory research may impact the security of cryptosystems, but not all results do.


That doesn't quite generate a prime. It generates a number that's a prime with a very high probability. There's always a small chance that it's not prime but it's good enough given the tradeoffs needed to verify that it's prime with 100% certainty.


Yeah, sorry perhaps I shouldn't have made such a specific sounding claim. I'm not an expert on this topic, but was pretty sure I had heard from reputable sources in the past that the Riemann Hypothesis had some bearing on the distribution of prime numbers. And it feels safe to say that this could have practical implications for cryptography. But maybe I should just leave it to the experts :).


Small correction: cryptographic algorithms don't depend on "prime numbers being hard to find", as they are not hard to find. Say you want to sample a 1024-bit prime. Then if you sample a random 1024-bit integer, it will be prime with probability 1/1024, roughly. This is a consequence of the prime number theorem [1]

Some crypto (namely, RSA) depends on on composite numbers being hard to factor, which is a different problem.

[1]: https://en.wikipedia.org/wiki/Prime_number_theorem


RSA depends on large prime factors being hard to recover from their product.


Yes, that is what "factoring a composite number" means, and that's what I said in the last sentence.


Crucially, the factors involved have to be very large.


If it were just that, it would be trivial to break. It's the fact you generate the key after a modulus operation that makes it difficult to recover.


Nope. The public key is not reduced mod anything in RSA. The large semiprime the user calculates is emitted explicitly as part of the public key and is used as a modulus in RSA operations.

Factoring that large integer directly yields the user's private key.


Yep.. should not have done that from memory. I had the private exponent in mind and forgot about the simplicity of the actual "RSA problem."


> depend on prime numbers being hard to find

That depend on large semiprimes being hard to factor.


No you can't make a startup off this result now get back to optimizing ads.


How about a SaaS log parsing startup?




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: