I understand that given solutions for solving a discrete logarithm problem are on the order of 𝑂(2𝑛/2), ergo, 256bit private keys based on 25519 or secp256k1 have an effective bit strength of 128bits.
I was wondering if anyone could explain how one can know the largest size private key supported by a curve. Is it to do with the curves prime field? I'm just trying to learn a bit more about ECC.
As people slowly look at RSA 3072+ as archaic and not strong enough, I wonder how long before 128bit strength ECC goes the same way.
Do we have any non NIST (NSA backdoored :) ) curves which support 512 bit private keys (yielding 256bit security?).