How do I get the equivalent strength of an ECC key? I know how to calculate the comparable symmetric strength of an RSA modulus: calculate the running time for a field sieve. This is how NIST gives approximate symmetric sizes for asymmetric algos in their publications: for RSA you can calculate running time of the field sieve:
$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$
What's the equivalent for ECDHE? Eg. what is the running time for the best known algorithm for attacking a given ECC curve?
RFC 4492 states:

the following table gives
approximate comparable key sizes for symmetric- and asymmetric-key
cryptosystems based on the best-known algorithms for attacking them.





Symmetric
ECC (binary curve)
ECC (prime curve)
DH/DSA/RSA




80
163
160
1024


112
233
224
2048


128
283
256
3072


192
409
384
7680


256
571
521 (not a typo)
15360




How can I replicate the ECC column's numbers?
Edit: some some research, the paper mentioned in the RFC now 404s but a copy found at http://infoscience.epfl.ch/record/164526/files/NPDF-22.pdf mentions:

2.6.3. Attacks. A DLNFS equivalent or other subexponential method to attack EC
systems has never been published. The most efficient method published to attack EC
systems is Pollard’s parallelizable rho method, with an expected run time of 0.88√q group operations.

However I still don't know how to replicate the results: an elliptic curve has P and Q but how do I know what Q is, for, eg, secp521r1?
Edit: Deirdre Connolly on Twitter mentioned an approximation:
$log_2(0.88 \cdot \sqrt{2^{n}})$
Which matches the RFCs results. Will do some more research and post it as an answer in the next few days if she doesn't.
The security level of an elliptic curve group is approximately $\log_2{0.886\sqrt{2^n}}$. You can use this to approximate the security level of a $n$-bit key, eg:

$\log_2{0.886\sqrt{2^{571}}} = 285.32537860389294$

The real computation (at least for curves over a finite field defined by a prime $p$) is $ \log_2{\sqrt{\pi/4}\sqrt{ℓ}} $, where $ℓ$ is the order (number of points) of the subgroup of points on the curve generated by the public base point. The size of $p$ determines the upper bound of $ℓ$, though it is not exactly the upper bound itself, it's generally pretty close. So for example, Curve25519 has an $ℓ$ of about $2^{252}$, so:

$ \log_2{\sqrt{\pi/4}\sqrt{2^{252}}} = 125.82537860389293 $

Our approximation based on the ECC key size gets us pretty close to this:

$\log_2{0.886\sqrt{2^{256}}} = 127.82537860389293 $

As otus notes below, Koblitz curves are slightly different.

The strength of any ECC key is bound to the strength of the underlying curve and domain parameters, and in general all the valid keypairs generated for a specific curve should have the same size/strength. There are some points that are invalid and should not be used, but your ECC implementation should handle that for you.

More info on determining the runtime of Pollard's Rho and thus the theoretical security level of various curves at SafeCurves: http://safecurves.cr.yp.to/rho.html