4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Titanlord Jul 25 at 10:31
  • 1
    $\begingroup$ 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. $\endgroup$ – corpsfini Jul 25 at 10:36
  • 1
    $\begingroup$ 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$. $\endgroup$ – corpsfini Jul 25 at 11:57
  • $\begingroup$ 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$? $\endgroup$ – Titanlord Jul 25 at 13:52
  • $\begingroup$ $(-1) + 486662\cdot (-1)^2 + (-1)$ is not a square so there is no point $(-1, y)$ on Curve25519. $\endgroup$ – corpsfini Jul 25 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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