# baby-step, giant-step vs Pollard-rho

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?

• 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?
– SEJPM
Jan 31 '18 at 18:52

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.