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

I also commented on NP=P and the Number Field Sieve algorithm recently involving RSA here:

But I want to actually clarify a couple of things I said. I in fact was slightly incorrect about the complexity of the NFS algorithm itself.

https://en.wikipedia.org/wiki/General_number_field_sieve

The complexity in big-O notation is actually that top equation, that isn't the algorithm itself.

I'll point out this quote because that equation simply for complexity notation itself is fairly ridiculous to distinguish:

    The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input.

So it's not polynomial, but it's also not quite exponential. Solving P=NP actually COULD speed up the NFS algorithm. Now the question is, how much?

While factoring numbers might actually be solvable in polynomial time, I don't think it wouldn't matter much. Polynomial equations can still be difficult if the number of polynomials needed to solve the equation are high, such as if the number of bits can cause the polynomial equation found to have millions of polynomials. In that instance, if increasing the bit size increased the number of polynomials required to solve the equation (probably I think? I mean we are talking about pure speculative solutions here so who knows what the solution would end up being), we would just end up using RSA 8192-bit or 16384-bit to slow the factoring process down again.

Then again, RSA on larger bit keys slows down the encryption process itself, but we already are under the assumption that this is slow and that is why we use hybrid encryption for things like TLS. So while P=NP would likely affect how we configure RSA on servers, it would likely just end up being a patch to services that use TLS or RSA (many have maximum bit settings at 4096 for instance) and a requirement that we regenerate all of our private keys. It's happened before (all UNIX servers had to do this with Heartbleed), we can do it again. Some sleep will be lost for a few weeks by certain people and then life would move on.