0
$\begingroup$

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

  • 1
    It's rather $p+1 + O(\sqrt{p})$.2011-09-10
  • 0
    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!)2011-09-10
  • 0
    Another quick question: why, for every point $P$, there exists an integer $k$, such that $k*P=O$?2011-09-10
  • 0
    @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)2011-09-10
  • 0
    But why this repeated addition can't result in a cycle of values?2011-09-10
  • 0
    @ted.k: Points under addition form a [group](http://en.wikipedia.org/wiki/Group_%28mathematics%29), and in a group, if $k\cdot P = (k+m)\cdot P$, then $m\cdot P = O$ (just add the inverse of $k\cdot P$ to both sides). So, yes, they *do* form a cycle, it's just that the cycle always includes $O$. PS: In order to alert a specific user of your comment, you can use `@...`; otherwise, they might not see it.2011-09-10
  • 0
    @Arturo Magidin: thanks :)2011-09-10

1 Answers 1

1

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.