ECC algorithm pollard's $\rho$ complexity

Question

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?

This Wikipedia article states 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.)

Answer 1

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).

Answer 2

If I am not wrong, then any discrete logarithm problem over a generic group of order $p$ has a lower bound of $\Omega(\sqrt{p})$ by the seminal work of Shoup, so you cannot have a deterministic algorithm that runs in time less than $\Omega(\sqrt{p})$.

However, this leaves the question of randomized algorithm completely open. The complexity of $O(\sqrt{p})$ in the $\rho$-method comes because for the iterative function (cycle-finding function) that they have chosen, it takes about $\sqrt{p}$ times to get a collision. Intuitively you can understand this complexity in an alternative way: the cycle finding function reduces the space of the group for having a collision to $O(\sqrt{p})$ and so a scan over this reduced space should give you the correct answer. Otherwise, if you are acquainted with birthday paradox, it is just the complexity of finding collisions by picking two random numbers. Now $n=pq$, two equal length prime gives you $O(n^{1/4})$. My understanding is that the $(\log n)^c$ factor is due to computing the random bit used in the above randomized algorithm, but some analysis needs to be done.