3
$\begingroup$

I'm studying algorithms that solve the discrete logarithm problem over elliptic curve. Reading online, it seems that people use the bsgs algorithm when the order of the curve is "low" and P-rho when it's "high".

But nobody says how much is "low" and "high", where I can find some good estimation? Is this true?

$\endgroup$
  • $\begingroup$ It appears that Pollard-Rho is a (little) bit harder to implement than BSGS. Can you give example(s) of BSGS being "preferred" for "small" orders? $\endgroup$ – SEJPM Jan 31 '18 at 18:52
2
$\begingroup$

BSGS algorithm requires huge storage space for curves with large order. This storage requirement usually exceeds the total available storage capacity across the whole world by several orders of magnitude.

So, finding an estimation depends on how much memory is available for you. Since you need to store all the generated points in a hash table for BSGS. If each point requires k-bits of storage and the curve is of order n, the storage requirement is $k * \sqrt{n}$ bits.

Eg: If each points require 32 bits of storage and the curve has order $10^9$ then total storage requirement is approxmiately 4 GB.

$\endgroup$
  • $\begingroup$ Most collision search can be reorganized with little memory, using distinguished points techniques, and parallelized on loosely connected machines. See Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Application, in Journal of Cryptology, 1999. I do not see why BS/GS would be an exception. $\endgroup$ – fgrieu Apr 9 '18 at 14:12
  • 1
    $\begingroup$ The Pollard's Rho algorithms is an improvement of the BSGS algorithm. Parallel Collision Search, in turn is an improvement of the Pollard's Rho method. So when you use the distinguished points method to detect a collision, it is no more BSGS, but Pollards Rho method. When you parallelize that, it becomes Parallel Collision Search $\endgroup$ – bilinbs Apr 11 '18 at 4:55

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.