4 ms·
Conjecture from the first link: "Raising questions about other problems. This a surprising result. Is a similar result for factoring around the corner? [...] P
by isomorphic 11y ago
Conjecture from the first link: "Raising questions about other problems. This a surprising result. Is a similar result for factoring around the corner? [...] Placing factoring in this complexity class would be a huge difficulty for cryptography."
If factoring is indeed in the quasi-polynomial class, the above may well be the understatement of the decade.
- shpx 11y agoIf this really is the case (and I'm highly skeptical), switching from 4096 bit to megabit or gigabit keys would buy us atleast a few years. But all previously encrypted messages would effectively become plain text to anyone with the foresight to save them.
- moyix 11y agoYeah. But as Scott Aaronson points out, GI has a very different feel to factoring. A randomly chosen number will be hard to factor, but it's actually quite hard to come up with examples of GI that are hard: > But then again, in practice, graph isomorphism has already been “basically in P” for decades! If you have two large graphs for which you actually need to know whether they’re isomorphic, just download NAUTY and run it. > This contrasts with the case of factoring, for which I’d personally say that it remains much less clear whether it should or shouldn’t be in P. http://www.scottaaronson.com/blog/?p=2521#comment-889824 http://www.scottaaronson.com/blog/?p=2521#comment-889824
- isomorphic 11y agoWell, we're resting at least a trillion-USD economy on that "much less clear"; probably more. Given that, bad actors are properly incentivized to work on factoring, and we can take comfort that we haven't yet heard any evidence yet of a (quasi-) polynomial solution. That is assuming someone couldn't keep something like that a secret.