Curve25519/Montgomery curves points with order 8

Question

I found this post about Curve25519. It states, that there are only 5 points with a very low order. With this paper I was able to understand, how the points with order 2 and 4 were computed. My question is: How to compute the points with order 8?

Answer 1

Curve25519 has order $8\cdot q$, and we want a point of order $8$. This is the laziest solution I can think of:

1. Generate a random point $P$ on the curve;
2. Compute $Q = [q]P$. This point has order $1$, $2$, $4$ or $8$.
3. If $Q$ is not of order $8$, go back to step 1.

A sample code to see the points we get:

E = EllipticCurve(GF(2^255-19),[0,486662,0,1,0])
for i in range(20):
    P = E.random_element()
    Q = P.__mul__(2^252 + 0x14def9dea2f79cd65812631a5cf5d3ed)
    print (Q.order(), Q)

Expect a few attemps until a point of order $8$ is found.

---

Another way to do this is to use division polynomials.

Just giving the general idea about them. There is a series of polynomials whose roots are related to torsion points. Basically, the points $P$ such that $[n]P = \infty$ have their $x$-coordinate as roots of a polynomial.

However, those roots can be over an extension field, so they do not correspond exactly to points on the elliptic curve over the base field.

Using SageMath, we can find the $8$-torsion points of Curve25519:

sage: p = 2^255 - 19                                                                                  
sage: E = EllipticCurve(GF(p), [0,486662,0,1,0])                                                      
sage: E.division_polynomial(8).roots(multiplicities=False)                                            
[0,
 57896044618658097711785492504343953926634992332820282019728792003956564819948,
 39382357235489614581723060781553021112529911719440698176882885853963445705823,
 325606250916557431795983626356110631294008115727848805560023387167927233504,
 1]

There is the point $(0,0)$ of order $2$, the next root corresponds to two points of order $4$ on Curve25519 over $\mathbf F_{p^2}$, the next two roots to four points of order $8$, and the last one to two points of order $4$.