Second stage of elliptic curve factorization via random walk/Pollard's rho in constant (or low) memory?

Question

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}$?

Answer 1

Brent's paper Some integer factorization algorithms using elliptic curves describes a "birthday paradox" ECM extension based on a random walk that only uses $O(\sqrt{r})$ group operations on the elliptic curve (see Section 6), however it is not space efficient. Cycle detection techniques do not apply because the iteration function used is not a deterministic operation on the elliptic curve modulo any of the (unknown) prime factors of $n$, and it is not clear how one might construct such a function.

One can apply the usual Pollard-$\rho$ approach to computations on the elliptic curve performed mod $n$, say using an iteration function where $Q_{i+1}$ is $2Q_i$ or $2Q_i+Q$, depending on the parity of the $x$-coordinate of $Q_i$ when viewed as an integer in $[0,n-1]$. This will eventually lead to a cycle, which can be recognized using standard techniques (e.g. Floyd's algorithm) with a space complexity of $O(\log n)$ bits. But the expected length of this cycle (assuming this iteration function actually approximates a random walk) is $O(\sqrt{m})$, where $m$ is the order of $P$ on $E(\mathbb{Z}/n\mathbb{Z})$, not $O(\sqrt{r})$.

Answer 2

As far as I know, it is still an open problem to get a space efficient second stage for ECM, and probably not possible. The same applies to the Pollard p-1 method (which can also be done with a second stage).

There is one issue that should be clarified: In the second stage one is hoping to have a point whose order is a prime r in the range B < r < B' where B is the "smoothness bound" from the first stage, and B' is the bound for the second stage. Rather than complexity depending on r or sqrt(r), one is looking for a method with complexity (B' - B) or sqrt( B' - B). The complexity O( sqrt( B' - B )) can be achieved using an FFT method, with large storage.

Now, the frustrating thing is that, in the second stage, one assumes one has an element g in the group with prime order r such that B' < r < B. It is natural to try to compute the order of g using Pollard rho in the usual way. But this involves branches (partitioning the group (mod p)) and there is no way to do this in a well-defined way (mod p) using information (mod N).

The genius of the Pollard rho factoring algorithm is to have a "random walk" function with no branches.

I don't want to scare anyone off thinking about this: but Pollard invented the p-1 method AND the rho and kangaroo algorithms. If it was easy to get a space-efficient second stage for the p-1 method or ECM then he'd have done it in the 1970s . . .