ECC algorithm pollard's $\rho$ complexity One of the methods to break a ECDLP is Pollard's rho algorithm. When ECDLP is defined over a finite field $F_p$, and given a relation $S=w.T$, where S and T are a member of $F_p$. Then ECDLP is to find w.

The algorithm is supposed to take a time $O(\sqrt p)$.

The authors say its exponential or subexponential, at best. How is it that way?

Is there any relation between w and p which makes it exponential?

Wiki article says without any citation:


  The algorithm offers a trade-off between its running time and the
  probability that it finds a factor. If n is a product of two distinct
  primes of equal length, running the algorithm for $O(n^{1/4} polylog(n))$
  steps yields a factor with probability roughly half.[citation needed]
  (Note that this is a heuristic claim, and rigorous analysis of the
  algorithm remains open.)
When we say an algorithm is 'exponential' or 'polynomial', when mean that the running time is bounded by an exponential or polynomial function of the size of the input in bits.  That is, the input of the function is not $p$, but $\log p$.  And so, $O(\sqrt p ) = O( e^{1/2 \log p})$ is bounded by an exponential in $\log p$.

Also note that the Wiki article is not talking about the Pollard rho algorithm applied to ECDLP, instead it is talking to Pollard rho applied to factorization.  For the Pollard rho applied to factorization, the time it takes is a factor of $p$, where $p$ is the smaller factor; hence, (because the factors are approximately the same length) $\sqrt p$ is roughly $n^{1/4}$ (with the $polylog(n)$ factor coming into place because Pollard rho isn't perfectly efficient in this scenario).