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

61–70 of 161 posts

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

#61

Post by khana »

golol wrote: post #57
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…

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.

[dead]

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

#62

Post by ZoomZoomZoom »

codeduck wrote: post #52
g15jv2dp wrote: post #41

Earlier quoted context omitted.

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…

The definitions given do not advance the explanation of the topic of TFA one bit but just boggle down the reader with irrelevant details. It's already not easy to digest by a casual reader, why make it harder for them? Just the mention of a "two-dimensional number" is already an utter fail, everybody knows you need two numbers for a 2D coordinate.

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

#63

Post by novaRom »

keepamovin wrote: post #25

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…

A generator of "all primes" is pretty simple and deterministic. But you cannot simply generate next prime given only prime n without recomputing its non-trivial remainders. That means just a binary representation of a number n doesn't provide enough information to make quick answer what is the next prime. You have to pre-compute some 'pivots' first. Basically, more complexity, but it's still simple and trivial, not even in NP.

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

#65

Post by mbreese »

PeeMcGee wrote: post #49
shinycode wrote: post #3

Earlier quoted context omitted.

From what I remember in my math class where we made those cryptography calculations by hand, the teacher many years ago said that the day we could guess prime numbers it will be a disaster because many cryptographic calculations are based on the premise that we can’t guess prime numbers. I don’t know if that changed ?

It's easy to find primes of a given bit length, and it's easy to multiply them together. It's hard to un-multiply a given number (public key) into its unique prime factors (private key).

But if we could more easily find primes, the search space for finding those prime factors would be significantly smaller.

In my mind, it’s not a question of easy vs hard… it’s a question of fast vs slow. The default algorithm for finding primes is pretty simple, but it takes a lot of math and time. If you reduce the time requirements, then we start to get into trouble.

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

#66

Post by guhbkji »

novaRom wrote: post #63
keepamovin wrote: post #25

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…

A generator of "all primes" is pretty simple and deterministic. But you cannot simply generate next prime given only prime n without recomputing its non-trivial remainders. That means just a binary representation of a number n doesn't provide enough information to make quick answer what is the next prime. You have to pre-compute some 'pivots' first. Basically, more complexity, but it's still simple and trivial, not e…

> not even in NP

This is incorrect. Integer factorization is NP-intermediate. Very much “in NP”.

https://en.m.wikipedia.org/wiki/NP-intermediate

Also, saying factorization lacks “complexity” because sieves exist misunderstands both concepts.

> In order to talk about complexity classes such as P, NP, and co-NP, the problem has to be stated as a decision problem.

> Decision problem (Integer factorization) — For every natural numbers n and k, does n have a factor smaller than k besides 1?

> It is known to be in both NP and co-NP

https://en.m.wikipedia.org/wiki/Integer_factorization#:~:tex....

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

#67

Post by bjoli »

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?

If anything, ECC is probably easier to break with qc. Shor's algorithm works "better" for discrete logarithms than for prime factorisation. "Better" as in requiring a smaller quantum computer. Still way beyond what is available today.

The reason for switching to ECC is speed and key size. The NSA recommends 3096bit rsa keys for 128 aes, but only 256 bit ecc keys for the same security against traditional attacks.

They also went ahead and recommended 348bit keys for ecc, but I don't know if something like that is widely used anywhere. Curve448 is nice but slow. Curve41417 is fast but largely unused.

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

#68

Post by TheCondor »

tommiegannert wrote: post #7
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…

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.

Arguably, we know a lot more about elliptical curves than prime number theory too. There have definitely been a lot more folks working on it.

There are other algorithms, NIST has a post-quantum project. There are options, but it’s a lot more than having some algorithms, we need protocols and they are still a bit off. Prime factorization isn’t going to get easier or faster though. There might be another attack or approach to attacking, some other numerical break through that leads to faster rsa cracking might be found but it’s hard to imagine it being that practical.

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

#69

Post by robertlagrant »

atemerev wrote: post #46
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 industry couldn’t even prepare for a bad Crowdstrike update. And yet, it figured things out in a few days or so. The ability to prepare for catastrophic scenarios is overestimated. The ability to survive them is underestimated.

This would be a lot worse than that. Crowdstrike was bad because everyone lets relatively untested code straight into the Windows kernel - i.e. known incompetence of approach. This would be bad despite massive care taken to have the right approach.

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

#70

Post by alkyon »

riidom wrote: post #50
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...

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.

Sack's spiral is a variant of Ulam's spiral, he discovered in 1963 using MANIAC II.

Edit: https://en.wikipedia.org/wiki/Ulam_spiral

Post reply on HN