a thoughtful web.
Good ideas and conversation. No ads, no tracking.   Login or Take a Tour!
comment by rob05c
rob05c  ·  3380 days ago  ·  link  ·    ·  parent  ·  post: P Vs. NP: The Assumption That Runs The Internet

    the day after someone proves P = NP, all asymmetric crypto suddenly breaks

Maybe. But what if someone discovers a symmetric algorithm for which the polynomial exponent is Graham's Number?

That is, there are polynomial exponents for which it would take half the electrons in the universe, until the heat death of the universe, to compute relatively small n. We just have to find one.





dingus  ·  3380 days ago  ·  link  ·  

Obviously an algorithm such as that is just as ineffective as an exponential algorithm, but it's important to know if you can turn an exponential-time algorithm into a polynomial-time algorithm because it means that, in 10 years, you might find a symmetric algorithm for which the polynomial exponent is within the realm of breakability. In the meantime, if someone finds a faster exponential-time algorithm you just double the key size.