The second stage of elliptic curve factorization has the drawback of large memory usage.
Let $n=pq$, $E(\mathbb{Z}/n\mathbb{Z})$ is elliptic curve and $P$ point on $E(\mathbb{Z}/n\mathbb{Z})$.
On $E(\mathbb{Z}/p\mathbb{Z})$ the order of $P$ is small $r$.
Set $Q=kP$ for pseudo-random $k$. On $E(\mathbb{Z}/p\mathbb{Z})$ one can solve the discrete logarithm $Q=xP$ in time $O(\sqrt{r})$ and constant memory using Pollard's rho algorithm (more precisely one can find $aP=bQ$ if $r$ is unknown)
basically by doing random walks and exploiting the birthday paradox.
The question is:
Working on $E(\mathbb{Z}/n\mathbb{Z})$ ($p,q$ are unknown) can one solve $Q=xP$ (or $aP=bQ$) on $E(\mathbb{Z}/p\mathbb{Z})$ using the rho algorithm in $O(\sqrt{r})$ and constant memory: note that $r$ can be significantly smaller than the order of $P$ on $E(\mathbb{Z}/n\mathbb{Z})$.
The only significant choice appears to be the random walk.
I failed to do this yet discrete logarithms on $E(\mathbb{Z}/n\mathbb{Z})$ appear to work as expected.
Update: I suppose part of the problem with constant memory is that it may happen $Q_i \ne Q_j \mod n$ while $Q_i = Q_j \mod p$
If $E(\mathbb{Z}/n\mathbb{Z})$ were a ring, one could simply iterate
(A) $Q_{i+1}=Q_i^2+c$.
Would it be possible instead on an elliptic curve to work in some ring where (A) would be trivially stage 2 and stage 1 would be $Q_1 = k P \ k \in \mathbb{N}$?
