4

Given a elliptic curve over $F_p$ with the equation $E : y^2 = x^3 + Ax + B$, I want to find an isomorphous curve (quadratic twist) which can be written in the form $E': y^2 = x^3 + A'x + B'$ where $A'$ is a given.

Following Wikipedia's description of quadratic twists, this seems to be easy: since $E' : y^2 = x^3 + Ad^3x +Bd^2$ where $d$ is the twisting parameter. Solving $A'=Ad^3$ gives $d = \sqrt[3]{\frac{A'}{A}}$.

Checking with SAGE, however, I get completely wrong results. Given: $$\begin{align} p &= \mathrm{0xC302F41D932A36CDA7A3463093D18DB78FCE476DE1A86297} \\ A &= \mathrm{0x6A91174076B1E0E19C39C031FE8685C1CAE040E5C69A28EF} \\ B &= \mathrm{0x469A28EF7C28CCA3DC721D044F4496BCCA7EF4146FBF25C9} \\ d &= 2 \end{align}$$ I would expect $$A' = Ad^3 = \mathrm{0x487CE98D68E62BD64340E8CDA4EDF73017C8E976AE2FBD1C}$$ However, SAGE says that the twist with $d = 2$ is $$\begin{align} A' &= \mathrm{0xBDE1643020DCF116CAC0BA0BFFCC9E119EAABCD9AE2D23B2} \\ B' &= \mathrm{0x472F7598F817AD1ABF3C4F83B6BE0FEE11D68A776B9C52E1} \end{align}$$ How is this calculation done?

ccorn
  • 9,803
Jonas Mechtheim
  • 51

1 Answers1

3

First, since $d=2$ is a square $\bmod{p}$, you would not get a quadratic twist with that $d$ anyway.

Second, you got the twist formula wrong. Wikipedia's twist formula translates to $A' = d^2 A$, $B' = d^3 B$. See here for the detailed transformation. One nice aspect of this is that you will not need cube roots when given $A'$.

Third, SAGE applies a different transformation from the one on Wikipedia, apparently: $$\begin{align} d\,y^2 &= x^3 + Ax + B & x' &= x\,d^3 & y' &= y\,d^5 \\\therefore\quad y'^2 &= x'^3 + A' x' + B' & A' &= A\,d^6 & B' &= B\,d^9 \end{align}$$ So, to get SAGE's result, use Wikipedia's formula with $d^3$ instead of $d$.

Fourth, the SAGE documentation says:

If the base field $F$ is finite, $d$ need not be specified, and the curve returned is the unique curve (up to isomorphism) defined over $F$ isomorphic to the original curve over the quadratic extension of $F$ but not over $F$ itself.

That is, SAGE can simply choose some nonsquare $d$ itself because you can transform any nonsquare $d$ to any other nonsquare $d$ by scaling $y$ with a suitable factor.

Therefore I'd suggest that you simply use E.quadratic_twist() instead of E.quadratic_twist(d). Or at least make sure that $d$ is a nonsquare.

ccorn
  • 9,803