4
$\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?

Improve this question
$\endgroup$
1
  • $\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
    Commented Jan 31, 2018 at 18:52

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
2
  • $\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 ♦
    Commented Apr 9, 2018 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
    Commented Apr 11, 2018 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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