The answer to your question is, essentially, yes. The use of birthday paradox algorithms in the second stage of ECM is standard, and this can be done space efficiently using a random walk approach. The usual Pollard rho algorithm requires some minor modifications (using a slightly different choice of random walk, as you suggested), which are described in detail in section 6 of Brent's 1986 paper Some integer factorization algorithms using elliptic curves.
AVS
- 751
- 6
- 8