Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

Subquestions

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|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
show 6 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.