# Time complexity of DLP over Elliptic curve group

Consider NIST 192 elliptic curve group https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf. What is the time complexity of discrete log problem of it? Is it Pollard $$\rho$$ i.e $$\sqrt{N}$$, where $$N$$ is the size of the group?

• Welcome to Cryptography.SE What did you search 1? Also, the question is lack of knowledge on $N$, is it prime or smooth number, or ...? May 29 at 19:18
• P-192 is dead May 29 at 19:37
• How? What is the attack complexity?
– Sanu
May 29 at 20:19
• Parallel Pollard's $\rho$ did you read the necessary part on the links? May 30 at 9:25

Work complexity is $$\mathcal O(\sqrt n\,\log^2(n))$$ where $$n$$ is the group order². Time for attack is $$\mathcal O(\sqrt n\,\log^2(n)/d)$$, where $$d$$ the number of devices running in parallel. Each device needs little memory.
² The term $$\log^2(n)$$ reflects the cost of a group operation. That would be $$\log^2(h\,n)$$ in general, where $$h$$ is the cofactor. But $$h=1$$ for P-192, and $$h\le8$$ in all curves in the two NIST documents, so we can remove it from the equations.