If there is an n^(100^100) algorithm that solves an NP-complete problem, then P=NP, but public-key cryptography is still safe because for any practical n it's still too hard to break. There are also public-key systems that are based on NP-complete problems that are easily broken, because n is chosen too small.
Thank you for schooling me on this. I wasn't considering n^(100^100) problems.
You're thinking of P=BQP (which still falls into the seems-to-not-be-true-but-we-can't-prove-it category, but physics runs BQP already, so we don't need P=BQP for BQP attacks like Shor and Grover to be issue).