Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For a given elliptic curve over a finite field and a point $P$ on that curve, how can we bound its order (integer $k$, such that $k*P=O$).

share|improve this question
1  
It's rather $p+1 + O(\sqrt{p})$. –  Soarer Sep 10 '11 at 19:59
    
Thanks for cleaning up! I don't think you can do better than Hasse's Theorem. If you start with an elliptic curve over $\mathbb{Q}$ whose group of rational points is infinite cyclic, and you reduce modulo an appropriate prime, the group of points on the finite curve would be cyclic and may be as large as the Hasse bound, if I'm not mistaken (which I very well may be!) –  Arturo Magidin Sep 10 '11 at 20:23
    
Another quick question: why, for every point $P$, there exists an integer $k$, such that $k*P=O$? –  ted.k Sep 10 '11 at 20:28
    
@ted.k: Over a finite field? Because the number of points is finite, so the group of points is a finite group. In particular, by Lagrange's Theorem, $N\cdot P=O$ where $N$ is the total number of points. (P.S. Using * for multiplication when you have $\LaTeX$ available is rather heavy handed; better to use $\cdot$ (\cdot) in this case) –  Arturo Magidin Sep 10 '11 at 20:34
    
But why this repeated addition can't result in a cycle of values? –  ted.k Sep 10 '11 at 20:39

1 Answer 1

up vote 0 down vote accepted

The number of points in an elliptic curve $E$ over $\mathbb F_q$ is $\le q + 1 + 2\sqrt q$. So the order of every point is $\le q + 1 + 2\sqrt q$. That's about all you can say in the general case. If you can find the precise number of points $n$ in $E$, and if you can factorise $n$, then you can find the order of any point $P$ by checking, for every factor $k$ of $n$, whether $[k]P$ is the Point at Infinity.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.