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

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

-
I assume that by constant memory you mean $O(1)$ elements of $\mathbb{Z}/n\mathbb{Z}$, or $O(\log n)$ bits. –  AVS Mar 6 '11 at 14:24
@AVS yes, though something efficient like polynomial in log(n) will do too. –  jerr18 Mar 6 '11 at 14:34

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})$.

-
Thank you for the article, will look at it. At first glance it doesn't seem to use constant memory (as per the question) and the state of the art tool gmp-ecm uses gigabytes of RAM for large B_2. Am I am missing something? –  jerr18 Mar 6 '11 at 14:17
Actually, I may be missing something. It's been a while since I read this paper, and after looking at it more carefully I think I agree with you. The random walk approach does work and has the desired running time, but it is not clear how to detect collisions using a small amount of space. I will need to think about this some more... –  AVS Mar 6 '11 at 16:18
@AVS Thank you. If on the EC multiplication of points were defined, the question would be trivial via a squaring+c map. Can you replace EC by $X$ where $X$ will be a ring or a semiring and stage 1 of EC would work and in stage 2 you can use a map with multiplication for my question? Basically I want to replace "group" with "ring"/"semiring" in "Algebraic-group factorisation algorithm" here: en.wikipedia.org/wiki/Algebraic-group_factorisation_algorithm –  jerr18 Mar 6 '11 at 17:26
@jerr18 ...after further thought I don't see how to solve your problem using the approach described in Brent's paper. I have amended my answer to reflect this. –  AVS Mar 6 '11 at 19:08
Would it be enough for determinizing the walk pseudorandom map: Z/nZ -> {0,1} that holds in Z/pZ too (instead of using parity)? –  jerr18 Mar 7 '11 at 12:23

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 . . .

-
Thanks. Do you rule out the possibility of working in a ring where the quadratic map (like in rho factoring) will not need branches? –  jerr18 Mar 9 '11 at 11:52
I don't rule out anything. I certainly don't rule out the possibility that factoring (or DLP for that matter) might be "easy" on a classical computer. Maybe there is a different factoring algorithm which behaves similar to p-1 and ECM, but leads to computation in a ring. But the methods we're discussing in this post lead to computation in a group, and this seems to be an obstruction to a memory-efficient second stage. –  Steven Galbraith Mar 12 '11 at 10:06