Working in a ring with something similar to elliptic curve factorization?

2011-03-12T11:10:18Z

Elliptic curve factorization tries to factor integer $n=pq$ by working on an elliptic curve $E(\mathbb{Z}/n\mathbb{Z})$ and for a point $P$ computes $Q=kP , k \in \mathbb{N}$ hoping to find the point at infinity in $E(\mathbb{Z}/p\mathbb{Z})$

Is it possible the algorithm to work instead in a group in some ring defined over $\mathbb{Z}/n\mathbb{Z}$?

Using multiplication of elements will give improvements like deterministic random walk $\mod p$ or exploiting smoothness via computing $Q^k$.

Related question

Update

Here is an example:

Instead of working on $E(\mathbb{Z}/n\mathbb{Z})$ work in some ring $X$ defined $\mod n$.

Pick $P \in X$.

Stage one would be computing $Q=kP$ where $k$ is product of small primes. If this hits the additive identity $\mod p$ (and not $\mod n$) the algorithm is done. This step uses only addition of elements as in the EC case.

Otherwise extensions may be possible because multiplication $x y : x,y \in X$ is defined.

It may happen that the additive order $a$ of $Q$ $\mod p$ is relatively small. Set $Q_1=Q$ and do a random walk by iterating $Q_{i+1}=Q_{i}^2+P$. This seems analogous to Pollard rho factoring and the complexity is $O(\sqrt{a})$ in constant memory (because of the birthday paradox). Obstruction in the EC case is that there is no deterministic random walk $\mod p$.
It may happen that the multiplicative order $m$ of $Q$ $\mod p$ is B-smooth (divisible by only primes smaller than certain bound). Computing $Q^k$ where $k$ is the product of the primes up to the bound (and is divisible by $m$) will hit the multiplicative identity of $X \mod p$.

Note that both (1) and (2) are performed after stage 1.

There should be many possible choices for $X$ and its characteristic should not be a fixed function of the primes factors.

Working in a ring with something similar to elliptic curve factorization? - MathOverflow

Working in a ring with something similar to elliptic curve factorization?