Simple question and I’m fully aware of the other question, but I need the answer for curves in the twisted Edwards form and I suppose converting the curve and the point to the Weierstrass form would change the resulting order being computed (unless I’m wrong)…

  • $\begingroup$ Third question : the order of a point is the same as the curve’s order ? $\endgroup$ Commented Jul 7 at 16:53
  • $\begingroup$ neuromancer.sk/std/other/Ed25519 $\endgroup$
    – kelalaka
    Commented Jul 7 at 18:08
  • $\begingroup$ @kelalaka I’m afraid 1 of the curve I have in mind isn’t on the neuromancer database and thus had it’s order to be computed because it’s also undocumented. $\endgroup$ Commented Jul 7 at 20:14
  • $\begingroup$ Each curve may need a different Edward to Weistrass birational transformation. So how we can know what you have in your mind? $\endgroup$
    – kelalaka
    Commented Jul 8 at 7:34
  • 1
    $\begingroup$ Taking the standard birational transformation from Edwards to Montgomery form does not change the order (the map is a group isomorphism where defined). Moreover, in any group, the order of a point must be a divisor of the order of the curve, so there are only few choices for a point's order on the curve you are considering. $\endgroup$
    – yyyyyyy
    Commented Jul 10 at 8:13

1 Answer 1


The order of an element $P$ of a finite group is, by definition, the smallest strictly positive integer $k$ with $k\cdot P=\underbrace{P+P+\cdots+P}_{k\text{ terms}}$ equal to the group neutral. This order divides the group order (it's number of elements). To identify the order of a given finite group element, a general technique is thus to try all $k$ dividing the group order by increasing value, stopping at the first $k$ with $k\cdot P$ the group neutral. One optimization (not even indispensable here) adds caching of earlier computed $P_k=k\cdot P$, and for $k'$ multiple of $k$ compute $P_{k'}=(k'/k)\cdot P_k$. Further refinements can save on the cache size by exploring a tree according to the prime factorization of the group order.

The rest of this answer is restricted to twisted Edwards curves commonly used in cryptography $$E=\{(x,y)\in\mathbb F_p\times\mathbb F_p\ \text{ such that }-x^2+y^2=1+d\,x^2y^2\,\}$$ with givens: prime $p$ with $p\bmod 4=1$, integer $d$ with the Legendre symbol $\left(\frac d p\right)=-1$, order (number of elements) $|E|=h\,n$ with $h=4$ or $h=8$ and odd prime $n$. Artificially small examples are $(p,d,h,n)=(53,2,4,11)$ or $(73,5,8,11)$. The group law is: $$\bigl(x_1,y_1\bigr)+\bigl(x_2,y_2\bigr)=\bigl((x_1y_2+x_2y_1)/(1+d\,x_1x_2y_1y_2),(x_1x_2+y_1y_2)/(1-d\,x_1x_2y_1y_2)\bigr)$$

The order of an element $P$ of the curve is a divisor of the curve's order $|E|=h\,n$. It thus can only be one of $\{1,2,4,n,2n,4n\}$ if $h=4$, $\{1,2,4,8,n,2n,4n,8n\}$ if $h=8$. There are:

  • $1$ element of order $1$ : the neutral/point at infinity $(0,1)$
  • $1$ element of order $2$ : $(0,-1)$
  • $2$ elements of order $4$, of the form $(\pm j,0)$ where $j^2=-1$. $j$ can be found by Tonelli–Shanks.
  • $n-1$ elements of order $n$
  • $n-1$ elements of order $2n$
  • $2n-2$ elements of order $4n$
  • and additionally if $h=8$
    • $4$ elements of order $8$, which differ by the sign of $x$ and/or $y\,$; in the example $(p,d,h,n)=(73,5,8,11)$ these points are $(\pm25,\pm18)$
    • $4n-4$ elements of order $8n$

Here, from a curve element $P$ given as $(x,y)$, we can use this algorithm:

  • if $x=0$
    • if $y=1$, the order of $P$ is $1$, done.
    • if $y=-1$, the order of $P$ is $2$, done.
    • the point $P$ is not on the curve, done.
  • if $y=0$
    • if $x^2=-1$, the order of $P$ is $4$, done.
    • the point $P$ is not on the curve, done.
  • if $h=8$
    • compute $P_2=P+P=(x_2,y_2)$
    • if $y_2=0$
      • if ${x_2}^2=-1$, the order of $P$ is $8$, done.
      • the point $P$ is not on the curve, done.
  • compute $P_n=n\cdot P=(x_n,y_n)$, which is the most compute intensive part
    • if $x_n=0$
      • if $y_n=1$, the order of $P$ is $n$, done.
      • if $y_n=-1$, the order of $P$ is $2n$, done.
      • the point $P$ is not on the curve, done.
    • if $y_n=0$
      • if ${x_n}^2=-1$, the order of $P$ is $4n$, done.
    • if $h=8$
      • compute $P_{2n}=P_n+P_n=(x_{2n},y_{2n})$
      • if $y_{2n}=0$ and ${x_{2n}}^2=-1$, the order of $P$ is $8n$, done.
  • the point $P$ is not on the curve, done.

Note: for the two $h=8$ cases, we could alternatively precompute the coordinates of points of order $8$ and match $P$ and $P_n$ against these, rather than compute $P_2$ and $P_{2n}$.

Thinking about how to do this in SageMath: A problem is SageMath's EllipticCurve has no direct support for Edwards curves, twisted or not; only Weierstrass curves.

However there's an isomorphism to convert one into the other. That's discussed in MPHELL and in Dan NGuyen's Correspondence between elliptic curves in Edwards-Bernstein and Weierstrass forms. This would allow to use the build-in order for the element mapped from the twisted Edwards curve.

Another way is to just code the above algorithm; but we need to re-code at least the group law and, for best efficiency of the $n\cdot P$ part, point multiplication in a coordinate system minimizing modular inversions, e.g. projective coordinates where $(x,y)$ is represented by $(X,Y,Z)$ with $x\,Z=X$ and $y\,Z=Y$, see this page of the Explicit Formula Database.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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