4 Title, ring

# Second stage of elliptic curve factorization via random walk/Pollard's rho inconstant(orlow)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}$?

3 constant memory, ring is simpler

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 $Q_{i+1}=Q_i^2+c$.

2 tag random-walk

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

1