1

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

ted.k
  • 181
  • 2
    It's rather $p+1 + O(\sqrt{p})$. –  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
  • @ted.k: Points under addition form a group, 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. – Arturo Magidin Sep 10 '11 at 20:42
  • @Arturo Magidin: thanks :) – ted.k Sep 10 '11 at 20:43

1 Answers1

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.

TonyK
  • 64,559