Technically, if P=NP then we already have a working algorithm to solve NP problems in polynomial time.
It involves iterating through and running all possible programs ordered by length, giving them an increasing amount of time to run and checking (in polynomial time) if they produce the correct answer.
If there exists a program that finds the answer in polynomial time, this algorithm will eventually find it after wasting (at most polynomial) time iterating through other programs and tentative bounds.
If P != NP, it's still at least asymptotically optimal.
Hmm, but running 'all possible programs' is an exponential time operation (in the lengths of the programs)...
Yes, but as you note, "in the size of the program" and the size of {the program that solves 3-SAT in polynomial time if there is one} is a constant, so it's all constant.
Of course, that constant is astronomically unpractical.
I like the term "Galactic Algorithm" for these algorithms with unpractical constants.
https://rjlipton.wordpress.com/2010/10/23/galactic-algorithm...
No, P=NP does not immediately break crypto, because that relation makes no statement w.r.t. if those algorithms in P solving problems we thought were NP are easy to find. Or efficient. Just because the problem your adversary has to break is part of P doesn't make it easy.