MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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.

share|cite|improve this question
Seems like a very vague/broad question. You are familiar with Pollard rho and Pollard $p-1$? – Gerry Myerson Mar 12 '11 at 11:21
@Gerry yes, I am familiar with them. Any suggestions on improving the question? (I wouldn't care if it is closed) – jerr18 Mar 12 '11 at 11:37
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. – Felipe Voloch Mar 12 '11 at 21:40
@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. – Gerry Myerson Mar 12 '11 at 23:14
@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.... – Gerry Myerson Mar 13 '11 at 11:41

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.