Curve25519/Montgomery curves points with order 8

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?

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

• This is a pretty good idea and it works. Because I did not know this is possible, there is some math I don't quite know/understand. Can you shortly state, why this is possible? – Titanlord Jul 25 at 10:31
• It has nothing to do with elliptic curves, just only group theory. If you have an element $g$ of order $p_1p_2$ in a group, then $h = g^{p_2}$ is an element of order $p_1$ (since $h^{p_1}=g^{p_1p_2}=1$. On Curve25519, a random point is likely to have $q$ as a factor in its order, so by multiplying by $q$, the order of the resulting point has only a few possible values, which is a divisor of the curve cofactor. – corpsfini Jul 25 at 10:36
• A quick way to find the points of $8$-torsion in Sage is E.torsion_polynomial(8).roots(multiplicities=False). It will give the $x$-coordinate of the points. One of them corresponds to points on the curve over $\mathbf F_{p^2}$, but all the others adding the infinity point make the count to $8$. – corpsfini Jul 25 at 11:57
• Uhm something is weird. I can create this list of points with a low order, but the second points, which should have $x = -1$ can not be created. I did this using $F_p$ but not $F_{p^2}$. So why does this list with $E$ over $F_p$ contains $x = -1$? – Titanlord Jul 25 at 13:52
• $(-1) + 486662\cdot (-1)^2 + (-1)$ is not a square so there is no point $(-1, y)$ on Curve25519. – corpsfini Jul 25 at 15:52