4
$\begingroup$

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<p/4$.

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ – Ruggero Apr 9 at 12:47
  • $\begingroup$ @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). $\endgroup$ – fgrieu Apr 9 at 16:54
6
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$ – Mike Hamburg Apr 10 at 0:23
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ – fgrieu Apr 9 at 16:46
2
$\begingroup$

Answering on the subquestion:

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$

$\endgroup$

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.