This is a followup to my recent question Discrete Logarithm Challenges and Records.
I am interested in confirming my understandings from the answer to that question, stated below:
For a discrete logarithm problem in a generic group of size $N$ with no special algebraic structure, the best known attack is the Pollard's rho method. If memory complexity were not an issue (it is!) then Baby Step Giant Step which has the same time complexity (namely $O(\sqrt{N})$) would also have the same performance. I am assuming $N$ is prime or the largest prime subgroup of order $p$ has essentially the same order, or just replace $N$ with $p$ in the above estimate.
The above statement also applies to the Elliptic Curve Discrete Logarithm problem, for curves with no known shortcuts/weaknesses.
I use "best" in the sense of minimal time complexity. Brent observed that the parallelizations which split the computation seemed to suffer from the "square root effect", as mentioned on page 4 of Van Oorschot and Wiener's classic paper Parallel Collision Search with Cryptanalytic Applications. However this was overcome by Van Oorschot and Wiener. This implies that the overall computation they perform is comparable to the single machine instance. In any case, even with parallelization, the overall computation is of the order $O(\sqrt{N}).$
Are these statements correct?