0
$\begingroup$

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.

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

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

Improve this question
$\endgroup$
7
  • $\begingroup$ Seems like a very vague/broad question. You are familiar with Pollard rho and Pollard $p-1$? $\endgroup$
    – Gerry Myerson
    Commented Mar 12, 2011 at 11:21
  • $\begingroup$ @Gerry yes, I am familiar with them. Any suggestions on improving the question? (I wouldn't care if it is closed) $\endgroup$
    – jerr18
    Commented Mar 12, 2011 at 11:37
  • $\begingroup$ You can work with elliptic curves over any ring, using schemes. The factorization algorithm, however, uses the fact that the quotient rings are finite. So you'll end up restricted to ring of integers of number fields and function fields. In function fields, there are easier ways to factor. $\endgroup$
    – Felipe Voloch
    Commented Mar 12, 2011 at 21:40
  • $\begingroup$ @jerr18, question still not coming through. You mean you want to work in a ring, instead of in the group of an elliptic curve? But the method only requires $Q=kP$, so you'd only be using the group part of the ring, anyway. Or maybe you also want to use something other than $Q=kP$, something that uses both the addition and multiplication in the ring. Whatever, it's not our job to guess at what you are trying to ask. Voting to close. $\endgroup$
    – Gerry Myerson
    Commented Mar 12, 2011 at 23:14
  • 1
    $\begingroup$ @jerr18, that's better, now it's easier to understand what you want - but it seems more like a fishing expedition than an MO question. Still, maybe somebody knows something.... $\endgroup$
    – Gerry Myerson
    Commented Mar 13, 2011 at 11:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .