Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Breakthrough a step toward revealing hidden structure of prime numbers

science.org

Post reply on HN
Print view View original

11–20 of 161 posts

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#11

Post by staunton »

exe34 wrote: post #8
tommiegannert wrote: post #7

Earlier quoted context omitted.

I think this is where the move to elliptic curve comes in, and that seems well on its way. Both in signatures and handshakes (Diffie-Hellman). Perhaps it's not a one minute operation to DR, but I doubt everything would be open if RSA/DH was rendered insecure overnight. I know my SSH keys are a mixed bag right now.

does the move to elliptic crypto suggest that the people in the know expect prime factorisation to be broken soon?

It's to do with "if we ever have big/good quantum computers, prime factorization is doable" and with "let's use the new shiny things".

On a related note, someone might discover some elliptic curve math tomorrow and your CPU can break all that stuff just as well...

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#12

Post by temporary_name »

exe34 wrote: post #8
tommiegannert wrote: post #7

Earlier quoted context omitted.

I think this is where the move to elliptic curve comes in, and that seems well on its way. Both in signatures and handshakes (Diffie-Hellman). Perhaps it's not a one minute operation to DR, but I doubt everything would be open if RSA/DH was rendered insecure overnight. I know my SSH keys are a mixed bag right now.

does the move to elliptic crypto suggest that the people in the know expect prime factorisation to be broken soon?

https://en.wikipedia.org/wiki/Shor%27s_algorithm

As soon as quantum computers have enough qbits prime factorisation can be done very quickly. Not sure the timeline on that as there are a lot of challenges in the technology and it is hideously expensive, but a lot of the move away from RSA to elliptic curves is driven by readiness for quantum computing.

https://en.wikipedia.org/wiki/Post-quantum_cryptography

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#15

Post by opyate »

JackSlateur wrote: post #6
EMIRELADERO wrote: post #2

This got me thinking. Imagine this discovery led to a larger breakthrough on prime numbers that allowed easy factorization of large integers and effectively rendered public key cryptography such as RSA ineffective overnight, by allowing anyone with a consumer-grade CPU to crack any production-size key. Does the industry have DR plans for this scenario? Can the big players quickly switch to a different, unbroken encry…

The world has moved away from RSA etc to elliptic curves. Not everybody did, through. RSA is no longer the standard, and has not been for many years.

Still, plenty of old stuff was scraped/sniffed under the "store now, decrypt later" methodology.

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#17

Post by kamov »

temporary_name wrote: post #12
exe34 wrote: post #8

Earlier quoted context omitted.

does the move to elliptic crypto suggest that the people in the know expect prime factorisation to be broken soon?

https://en.wikipedia.org/wiki/Shor%27s_algorithm As soon as quantum computers have enough qbits prime factorisation can be done very quickly. Not sure the timeline on that as there are a lot of challenges in the technology and it is hideously expensive, but a lot of the move away from RSA to elliptic curves is driven by readiness for quantum computing. https://en.wikipedia.org/wiki/Post-quantum_cryptography

Elliptic curve cryptography can be broken by Shor's algorithm as well

https://arxiv.org/pdf/1706.06752

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#18

Post by fragmede »

temporary_name wrote: post #12
exe34 wrote: post #8

Earlier quoted context omitted.

does the move to elliptic crypto suggest that the people in the know expect prime factorisation to be broken soon?

https://en.wikipedia.org/wiki/Shor%27s_algorithm As soon as quantum computers have enough qbits prime factorisation can be done very quickly. Not sure the timeline on that as there are a lot of challenges in the technology and it is hideously expensive, but a lot of the move away from RSA to elliptic curves is driven by readiness for quantum computing. https://en.wikipedia.org/wiki/Post-quantum_cryptography

sgt101 posted a good comment about this a couple months back: https://news.ycombinator.com/item?id=40187560

tl;dr: not in our lifetime.

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#19

Post by taneliv »

wood_spirit wrote: post #9

I’m curious as I hadn’t seen it before and it’s gripping: Is the patterns showing in a polar plot of the prime numbers a recent discovery or is it long known and just used as an illustration? What is it called and what is its history?

https://en.wikipedia.org/wiki/Ulam_spiral for more reading, Sacks spiral is from 1994.

Re: Breakthrough a step toward revealing hidden structure of prime numbers

#20

Post by jhncls »

throwaway81523 wrote: post #4

This is from May and there was a better article in Quanta already discussed here. https://www.quantamagazine.org/sensational-proof-delivers-ne...

Discussion: https://news.ycombinator.com/item?id=40981272 There are 6 comments; the last one is clearly the most interesting: a link to a discussion by Terence Tao https://mathstodon.xyz/@tao/112557249982780815

Terence Tao also provides links to a presentation by James Maynard and Larry Guth: https://www.ias.edu/video/new-bounds-large-values-dirichlet-... and https://www.ias.edu/video/new-bounds-large-values-dirichlet-...

Post reply on HN