# Using Sagemath, how to exactly find out what the order of a point of an elliptic curve in the twisted Edwards form is?

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)…

• Third question : the order of a point is the same as the curve’s order ? Commented Jul 7 at 16:53
• neuromancer.sk/std/other/Ed25519 Commented Jul 7 at 18:08
• @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. Commented Jul 7 at 20:14
• Each curve may need a different Edward to Weistrass birational transformation. So how we can know what you have in your mind? Commented Jul 8 at 7:34
• 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. Commented Jul 10 at 8:13

## 1 Answer

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.