Live data from Hacker News

Breakthrough a step toward revealing hidden structure of prime numbers

science.org

51–60 of 161 posts

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

#51
post #17

Earlier quoted context omitted.

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

... and easier than with RSA. Not that it would make a significant difference.

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

#52

[flagged]

Instead of expressing your knowledge and superiority by metaphorically rolling your eyes without contributing anything, how about you give a better explanation? Because honestly, I find these two kind-of "okay". And because this is HN, based on past experience, I need to preface with the fact that I'm a professor of math. So no need to start by questioning my knowledge on the topic, just get straight to the point.

> So no need to start by questioning my knowledge on the topic, just get straight to the point.

Undergrad physics, so you are obviously more versed in the field than I am.

But, speaking as someone with some small background in this, I would hope that an article on 'science.org' that mentions Gauss and Riemann would go into slightly more detail than i = sqrt(-1). Even a two-liner description of the real and imaginary plane would be an improvement and would possibly motivate people who knew very little about the area into going and researching. The entire article is about possible periodicity in prime numbers - why, then, omit one of the most important things about complex numbers and their relationship to periodic systems? Euler's formula is a beautiful thing, and I say that as a luddite.

And as for the harmonic analsys as "something in physics used to separate sounds and their notes" - I mean... that's like saying "Moby Dick" is a book about a whale. Yes, it's technically correct, but there is such a lost opportunity to describe just how all-encompassing Fourier Analysis is and how it naturally ties back to the complex numbers mentioned previously.

So, as demanded, here:

  For inputs, the function takes complex numbers, which are two-dimensional numbers with one coordinate on the real number plane and the other on the so-called "imaginary" plane.  Complex numbers are fundamental to the description of many periodic systems such as waves, cycles, orbits etc.

  harmonic analysis, which is a discipline that originated as the study of the composition of sound but was extended by mathematicians like Taylor and Fourier into a broad system of numerical analysis that is widely used in everything from number theory to neuroscience.
It would have taken very little additional effort, but the results would be rather different - showing paths forward rather than walls saying "this is all that there is to this".

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

#53
Every time I hear about James Maynard it really solidifies my opinion that he's one of those once in a generation geniuses. He's already contributed so much to prime number theory, it really feels like there might be a proof of the Riemann Hypothesis within my lifetime.

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

#54

Earlier quoted context omitted.

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.

You can’t imagine how many places I’ve seen “Elliptic curve certificates are not supported” as recently as this year. It’s the IPv6 of the security world.

That's because certificates are all about authentication not encryption. There is no real reason to move away from RSA for authentication. The reason that TLS moved away from RSA for encryption is that it is awkward to do forward secrecy with RSA due to the slowness of generating new RSA keypairs. In practice you would want to generate a new RSA keypair every, say, hour on the server and then somehow get it down to the cryptography level for use. Totally doable, but a different way of doing things.

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

#55
post #22

Earlier quoted context omitted.

Since no one mentioned, a major reason to prefer elliptic curves is that you can get equivalent security for much smaller key sizes.

And the key consituents don't have to be prime. That use of heuristics has always scared me a bit.

Nit-pic: the key constituents only need to be co-prime rather than absolutely prime, though in practise this makes little or no difference.

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

#56

People always think the structure of primes is complex, but it's not really, it's just a recursive structure of the magnitude gaps not landed on by multiples of previous gaps. It doesn't make it easier to "predict" without tracking all prior gaps, but it's not essentially a complex structure. Kind of funny that like such a simple structure is so elusive. Sorta like how the 3n + 1 sequence gives rise to such complexit…

[flagged]

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

#57

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…

I think someone working in cryptography will worry about a sudden number theory breakthrough that allows for breaking of cryptography as much as a someone working in the energy sector will worry about a sudden physics breakthrough that allows for practically free energy cold fusion energy.

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

#58
post #50

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

I am a bit disappointed that the article doesn't explain what the introductory illustration about Sack's spiral has to do with any of this.

[deleted]

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

#59

Earlier quoted context omitted.

I think that misses the point which is that the simplicity is overlooked in the common descriptions of primes as "random" or a great "mystery".

Yes, it’s difficult to predict where such an understanding might lead. If it reframes and redefines all of number theory, then we might call it one component of the foundational theory of number theory. Analogously, if someone proves that P = NP, then that will be great, but the significance of lambda calculus and Turing completeness will remain. If the proof is constructive and practical, we’ll just have to repriori…

> if someone proves that P = NP

> we’ll just have to reprioritize and update the list of algorithms we teach to undergrads, issue performance-enhancement updates to some software libraries, and patch any security vulnerabilities.

Wow, your optimism sure is something.

What are you patching and with what?

How do you “patch any security vulnerabilities” when said vulnerability is “all of our security research, except one time pad, is now so obsolete we are unsure if security based on computational complexity is at all practical anymore”?

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

#60
post #57

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…

I think someone working in cryptography will worry about a sudden number theory breakthrough that allows for breaking of cryptography as much as a someone working in the energy sector will worry about a sudden physics breakthrough that allows for practically free energy cold fusion energy.

free energy still needs to be distributed and solving free energy does not solve the balance of the grid. Dunno about Cryptographers.
Post reply on HN