Complexity

People often confuse symmetric and asymmetric encryption, particularly with regard to the key length. There are, however, fundamental differences between these two distinct encryption schemes. Their key lengths cannot be compared in a straightforward way.

In symmetric encryption, the complexity C (the key space, which attackers have to search) is basically identical to the key length. In asymmetric encryption, C is much lower than the key length as a consequence of the different mathematical algorithm required to allow an asymmetric encryption scheme at all.

The fastest method for searching the key space of, e.g., the RSA encryption technique, is of course still exponential (and the problem is presumably still NP complete), but the exponent is sublinear in the key length n in bits.

The left figure shows C (the effectice key length) of the RSA algorithm vs. n. As you see, the complexity of AES 256 (the NSA "top secret" classification) is out of reach for RSA.

The right figure shows the same thing assuming the existence of a quantum computer with a sufficient number of qubits (right now, 8 qubits are the state-of-the-art). You see that working quantum computers would render asymmetric encryption into a relict of the stone-age (they would also accelerate decryption of AES and the likes, since that scales as O(n^½). This attack, however, is easily counteracted...just double your key length.)