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

Let $n$ be composite with unknown factorization.

Can one efficiently find elliptic curve $E$ over $\mathbb{Z}/n\mathbb{Z}$ and a point $P$ on $E$ of known order $m > 5$?

$P$ should be nontorsion when lifted to $\mathbb{Q}$, so to avoid such cases one may consider $m$ larger.

$E$ might be singular (though better not be).

What I know

Singular cases like $E : y^2 = x^3$ are easy.

Singular cases when there is an isomorphism to a multiplicative subgroup are easy if one knows an element of known multiplicative order (say for Mersenne numbers), but this doesn't work for general $n$.

Tried division polynomials, but this leads to solving nonlinear equation over the ring so didn't work for me.


Are there $n$ of special form (except the described) for which it is possible?

The problem is not harder than factoring.

Is the non-singular case as hard as factoring?

share|cite|improve this question
You are not very precise with your terminology. If I understand correctly: Given $n$ and $m>5$, you want a Weierstrass equation $E$ with coefficients in $\mathbb{Z}$ and a point $P$ of infinite order in $E(\mathbb{Q})$ such that it has non-singular reduction modulo $n$ and it is of order $m$ in the reduction. Is that it ? – Chris Wuthrich Oct 30 '13 at 12:35
To say that $E$ is an elliptic curve over $\mathbb{Z}/n\mathbb{Z}$ means that it is a Weierstrass equation whose discriminant is invertiable modulo $n$. Note also that usually you can't lift points from modulo $n$ to the integers. – Chris Wuthrich Oct 30 '13 at 12:37
@ChrisWuthrich thanks for the comments. First, $m$ is not given, you are free to choose it (though arbitrary $m$ of course is better). Second, P need not be in E(Q) (though it might be), it must be in E(Z/nZ), i.e. after the reduction mod n. To avoid non-invertible denominator one can work with projective points after homogenization of the Weirstrass model. I mention the torsion because a rational torsion point will work for all $n$. – joro Oct 30 '13 at 12:59
Ah! So given $n$, you want to find a Weierstrass equation $E$ over $\mathbb{Z}/n\mathbb{Z}$ with a non-singular point $P$ on it whose order in $E(\mathbb{Z}/n\mathbb{Z})$ is larger than $5$. That is easy by the Hasse-Weil bound, isn't it? So I probably still do not understand the question. Sorry. – Chris Wuthrich Oct 30 '13 at 13:05
@ChrisWuthrich you understood exactly. I am not an expert but this is hard for me. Note that I can't do point counting to compute the order since the factorization of $n$ is unknown. And I can't construct curves of given order over Z/nZ. It is easy if $n$ were prime. – joro Oct 30 '13 at 13:14

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.