# Order of Edwards curve and its twist

In Mike Hamburg's Ed448-Goldilocks, a new elliptic curve (eprint 2015, WECCS 2015) it is studied untwisted Edwards curves in the prime field $$\mathbb F_p$$ $$E_d:\,y^2+x^2\,=\,1+d\,x^2\,y^2$$ with large prime $$p\equiv3\pmod 4$$ and the Legendre symbol $$\displaystyle\left(\frac d p\right)=-1$$.

The matching "twist" is $$E'_d:\,y^2-x^2\,=\,1-d\,x^2\,y^2$$

Constant $$d$$ is chosen with minimal $$|d|$$ such that the curve's order $$|E_d|$$ is $$4\cdot q$$ with $$q$$ prime, the twist's order is $$|E'_d|=4\cdot r$$ with $$r$$ prime, and $$q.

The paper uses prime $$p=4^{224}-2^{224}-1$$ and gives $$d=-39081$$,
$$q=2^{446}-\mathtt{8335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d_h}$$,
$$r=2^{446}+\mathtt{0335dc163bb124b65129c96fde933d8d723a70aadc873d6d54a7bb0d_h}$$

It holds $$|E_d|+|E'_d|=2\cdot p+2$$. Update: initially my experiments¹ differed by two but Mike Hamburg kindly pointed my mistake: I did not count the two points at infinity for $$E'_d$$.

The question (now) boils down to: Why $$|E_d|+|E'_d|=2\cdot p+2$$ ? And how do we find $$d$$ given $$p$$ ?

If the later is by mere enumeration of $$d\gets-j\cdot\displaystyle\left(\frac j p\right)$$ for incremental $$j>0$$ and checking $$q\gets|E_d|/4$$ and $$r\gets|E'_d|/4$$ are prime, how are these computed²?

¹ With $$p\gets4^i-2^i-1$$ for $$i\in\{4,5\}$$, I get $$\begin{array}{r|rrr} i&p&d&q&r\\ \hline 4&239&19&59&61\\ 5&991&-45&233&263 \end{array}$$

² This may be asking for Schoof–Elkies–Atkin adapted to Edwards curves. Pointer to an implementation also welcome.

• I'm not sure I follow your questions. There is a relation between the order of a curve and its twist, this makes their sum always equal to $2p+2$. I guess the order was computed through SEA on the Weierstrass version. Apr 9, 2021 at 12:47
• @Ruggero: my question now boils down to [A] asking proof/argument for $|E_d|+|E'_d|=2p+2$; [B] if there is a shortcut to screen out some $d$ that won't give prime $q$ or $r$; [C] exactly how we do SEA on Edwards curves (I vaguely guess we compute the order $|E'_d|/2$ of an associated Weierstrass curve but do not immediately get which, and have zero experience with SEA. The closest thing is these hints which I did not yet apply).
– fgrieu
Apr 9, 2021 at 16:54

Regarding the [B] and [C] parts of the question per the comments:

I'm not sure how exactly did Mike Hamburg find the curve, but from what I know it's usually easier to find the order of the matching Montgomery curve. Recall that Montgomery curves have the form $$By^2 = x^3 + Ax^2 + x$$. If $$B$$ is 1, then it fits into the generalized Weierstrass form, and most SEA algorithm implementations work with any curve in the generalized Weierstrass form. (If it's not 1 then you can easily map into a curve with $$B = 1$$, the same way that short Weierstrass curves can be mapped into $$a = -3$$)

So basically:

• Search for a Montgomery curve matching the criteria;
• Then convert it into Edwards form.

One optimization is to instruct SEA to quickly discard curves whose order it knows beforehand that have a small factor (other than 4 or 8), see the tors parameter of the ellsea PARI/GP function, for example.

The paper "A note on high-security general-purpose elliptic curves" has a Magma implementation of the process (though IIRC it uses a slightly different approach). RFC 7748 has a Sage script that also searches for a Montgomery curve (though it will probably be much slower, since it doesn't seem to support that optimization).

• This is correct. I implemented the behavior of ellsea with a negative tors parameter, to mean that the computation should abort if either E or its quadratic twist has order divisible by small primes other than tors. A derived patch was later merged into upstream PARI/GP by someone else (David Leon Gil maybe?). This functionality was at some point exposed in SAGE as well, but I'm not sure if it currently is. Then I wrote a script to loop through values of d, checking first that d is nonsquare and some similar residuosity checks to rule out other 2-torsion and 8-torsion points. Apr 10, 2021 at 0:23

Do your experiments count points at infinity? When $$d$$ is a quadratic nonresidue over $$\mathbb{F}$$, the curve

$$y^2 + x^2 = 1 + d x^2 y^2$$

has no points at infinity over $$\mathbb{F}$$. But if $$-1$$ is also a quadratic nonresidue, then the curve

$$y^2 - x^2 = 1 - d x^2 y^2$$

has two of them, roughly of the form $$(\pm\sqrt{-1/d}, \infty)$$.

• Ah, that's precisely my mistake. I edited the question to remove my bogus point count, and the which (formula for $|E'_d|$) part. Many thanks!
– fgrieu
Apr 9, 2021 at 16:46

Why $$|E_d|+|E'_d|=2\cdot p+2$$ ?

It follows from the definition of quadratic twist. In fact, let's consider all possible $$\tilde{x}$$ coordinates for points, that is all the values in $$\mathbb{F_p}$$, and an elliptic curve $$E$$ with equation $$y^2=x^3+ax+b$$, then:

Case $$\tilde{x}^3+a\tilde{x}+b\neq0$$:

So either $$\tilde{x}^3+a\tilde{x}+b$$ is a square and thus its square root provides us two points belonging to $$E$$, namely $$(\tilde{x},\pm\sqrt{\tilde{x}^3+a\tilde{x}+b})$$ or it is not a square. If it's not a square then it will be a square for the twist curve $$E'$$ of equation $$y^2=x^3+d^2ax+d^3b$$ with $$d\neq0$$ and non-square in $$\mathbb{F}_p$$, thus providing two points belonging to $$E'$$.

Case $$\tilde{x}^3+a\tilde{x}+b=0$$:

In this case the point lies on the $$x$$ axis and belongs both to $$E$$ and $$E'$$.

So, when you consider all possible $$\tilde{x}$$ values in $$\mathbb{F}_p$$, you have for each of them two points belonging to $$\{E \cup E'\}$$, if you add also the point at infinity for each curve, you end up with $$|E_d|+|E'_d|=2\cdot p+2$$