Working in a ring with something similar to elliptic curve factorization? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T11:52:34Z http://mathoverflow.net/feeds/question/58258 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/58258/working-in-a-ring-with-something-similar-to-elliptic-curve-factorization Working in a ring with something similar to elliptic curve factorization? jerr18 2011-03-12T11:10:18Z 2011-03-13T06:49:17Z <p><a href="http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization" rel="nofollow">Elliptic curve factorization</a> 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})$</p> <p>Is it possible the algorithm to work instead in a group in some ring defined over $\mathbb{Z}/n\mathbb{Z}$?</p> <p>Using multiplication of elements will give improvements like deterministic random walk $\mod p$ or exploiting smoothness via computing $Q^k$.</p> <p><a href="http://mathoverflow.net/questions/57548/second-stage-of-elliptic-curve-factorization-via-random-walk-pollards-rho-in-con" rel="nofollow">Related question</a></p> <p><strong>Update</strong></p> <p>Here is an example:</p> <p>Instead of working on $E(\mathbb{Z}/n\mathbb{Z})$ work in some ring $X$ defined $\mod n$.</p> <p>Pick $P \in X$.</p> <p>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.</p> <p>Otherwise extensions may be possible because multiplication $x y : x,y \in X$ is defined.</p> <ol> <li><p>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$.</p></li> <li><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$.</p></li> </ol> <p>Note that both (1) and (2) are performed after stage 1.</p> <p>There should be many possible choices for $X$ and its characteristic should not be a fixed function of the primes factors.</p>