A wild card here is the recent work in quantum computing, done at AT&T and reported in a recent post by Pal Vitanyi. With a specialized quantum computer (not clear yet whether one could economically built it, but it's theoretically possible) one can factor in polynomial time (computational class "QP", or something like that). If cycles on such a computer would be, say, 1,000 times more expensive than on your PC, then cracking the key would be 1,000*O(keysize^c) more expensive than generating it, not 1,000*O(c^keysize). Having a keysize of, say, 8 kbits instead of 1 kbit in this circumstance is not at all overkill; it makes a practical economic difference. Of course if your info is _very_ valuable and the polynomial is of small degree, even a large key size won't help much. If such a device was built, we'd want to switch to a cryptosystem whose inverse is not in QP; but some of our current communications would be compromised. If a QP machine is with even small probability feasible within the next few decades (or whatever your timeline of concern is), it makes sense to use larger key sizes.