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

  • $\begingroup$ The Handbook of Applied Cryptography says on Page 92 that it is $O(n^{1/4})$. I am not sure now where this poly-log factor came in to the picture! $\endgroup$ – Jalaj Apr 3 '12 at 14:26

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

  • $\begingroup$ Can you give more details on why $poly \log$ factor is there? I don't understand what efficiency has to do with it. Thanks in advance! $\endgroup$ – Jalaj Apr 3 '12 at 14:20
  • 1
    $\begingroup$ @poncho: Shouldn't they specify over what the complexity is said? I mean in a graph problem, generally the complexity is over the unmber of nodes and/or edges. Similarly, is it that for a number theory problem the complexity is generally measured for bits? $\endgroup$ – Vineet Menon Apr 4 '12 at 4:34
  • 1
    $\begingroup$ @VineetMenon: It's generally well understood that for algorithms that take a single integer parameter, the complexity of the function is generally expressed as a function of the size of that integer in bits. $\endgroup$ – poncho Apr 4 '12 at 10:41
  • $\begingroup$ @VineetMenon: Complexity of an algorithm is always measured in terms of input size. In group-theoretic algorithms, the input is group and so it is measured by the order of the group that defines the group. Same for the graph. You define the complexity of a graph-theoretic algorithm in terms of the size of the graph, which is the number of vertices and the number of edges. If you have a sparse graph, then you just specify the number of vertices, edges are considered to be $O(n)$. For a general graph, you need both edges and vertices as for any connected graph, $\Omega(n) \leq E(G) \leq O(n^2).$ $\endgroup$ – Jalaj Apr 4 '12 at 13:18

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.

  • $\begingroup$ This isn't true. The result is entirely theoretical, because in reality there is no such thing as a "generic group of order p". Every group in reality has a specific addition procedure that may be exploited. Either way, the result doesn't have anything to do with randomization. Shoup's work can also be extended to say that a randomized algorithm in a generic group of order p also runs in sqrt(p). $\endgroup$ – Nicholas Pipitone Dec 5 '18 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.