PKI = public key infrastructure, I don't think that's quite what you mean.
In any case, can factoring numbers be expressed as a NP-complete problem? I'm not sure about that. But even if it can't, it'd give problem solvers a new weapon to attack problems like that.
Sorry, it's really not what I meant to say. That was dumb. I should at least eat my cheerios in the morning before I look at the forums.
Anyway, the wikipedia article on this is pretty decent.
# The function problem version: given an integer N, find an integer d with 1 < d < N that divides N (or conclude that N is prime). This problem is trivially in FNP and it's not known whether it lies in FP or not. This is the version solved by most practical implementations.
They list two separate problems classified as "integer factorization" and this is obviously the relevant one to RSA.
P = NP if and only if FP = FNP
So yeah, if it's found P = NP, then FP = FNP and there'd be a polynomial time solution. I'm not sure if that means it could be trivially found, but sometimes people perform better when they know for sure the problem they're facing isn't impossible to solve. There was a graph theory problem (Is the inverse of a perfect graph always perfect?) that was unsolved for a long time. A professor had been working on a proof for two years or something, then a clever undergraduate at a different university solved it days after seeing the problem. The professor was obviously devastated, but within a day or so of finding out, he formulated his own proof. It was obviously too late by then, though. The undergrad stole all the glory from him.
