Ask HN: What happens if a fast integer factorization method is discovered?

3 points by chkhd 4 years ago | 2 comments

I am not a mathematician, but this seems like something that might have crossed the minds of math savvy people. Yes, this seems extremely unlikely, but as a thought experiment, what would come next?

Given the impact and implications this would have:

- How would anyone even go about publishing anything like this without literally breaking the world?

- Would this actually break the world?

- What if they were malicious? Could something like this sneak under the radar and escape to the dark web to be exploited by criminals?

- What if they were not malicious, but had non-scientific (cough) monetary, goals in mind, would there even be a way to somehow milk this?

- What if they were a scientist, purest of heart, how would they go about this?

- Wouldn't this have to be done anonymously for personal security reasons?

Watching the humanity over the past few years has been.. illuminating. I am not sure we are even remotely close to being set up to handle something like this.

What do you think?

mac3n 4 years ago |

There is at least one [science fiction] short story where this happens. Greg Egan, maybe?

There is a fast quantum factorization method, Shor's Algorithm. As far as we know, it is not yet practical. However, there is ongoing work on post-quantum cryptography that would be safe against such attacks.

The most likely users for a fast factorization algorithm that could break RSA encryption are nation-states. They would obviously keep this capability secret.

Nation-states have compromised many systems anyway, without needing to break this kind of cryptography. We are not really set up to handle this either.

thanatos519 4 years ago |

P != NP

... but answering your questions would make a great techno-thriller story.