4
$\begingroup$

I'm studying ECC, so this is focused on elliptic curves over finite fields. I've always seen the quadratic twist $E'$ of an elliptic curve $E$ defined as the elliptic curve with equation $dy^2=x^3 + ax + b$ for some quadratic non-residue $d$. Not a quadratic twist but the. Does this mean that there's some sort of equivalence between the twists of an elliptic curve? If there is no equivalence, what are the benefits of chosing one non-residue over another?

I think I understand why, for a given $x$, if there is no point in E with said $x$ there is one in $E'$. IIUC there not being a solution means that $x^3 + ax + b$ is a quadratic non residue. When multiplying that with $d^{-1}$ we get a quadratic residue and there exists a $y$ that satisfies the equation. And this should be true independently of $d$. But this does not get me anywhere close to claiming a strong relationship between twists with different quadratic non-residues.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

Over a finite field of odd characteristic, the quadratic twist of an elliptic curve is unique up to a change of variable. To see this, let $d$ and $d'$ be two distinct quadratic non-residues. Now note that $d'/d$ is a quadratic residue so that there exists some $c$ in the field with $c^2=d'/d$.

Now consider the set of solutions to the equation $$dy^2=x^3+ax+b$$ with the change of variable $(x,y)\mapsto (X,cY)$ we have $$d(cY)^2=X^3+aX+b$$ but $d(cY)^2=d(d'Y^2/d)=d'Y^2$ so that we have the set of solutions to $$d'Y^2=X^3+aX+b.$$

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Awesome answer. I was thinking of this transformation but thought it wasn't correct because it didn't appear to commute with the group operation. If you add two points P1 and P2, the x-coordinate of P3 depends on the slope of the curve through P1 and P2. So adding in two points in the original curve seemed to yield a different result from going to the twist with this transformation, adding there and then coming back to the original curve. The reason for this is that the transformation does not affect $x$. Am I missing something stupid? $\endgroup$ Commented Jul 18, 2022 at 12:56
  • $\begingroup$ @GastonMaffei: The usually quoted group law equations do not hold for the twisted form; in particular if we write $\lambda$ for the slope, then the law for $P+Q=R$ is $x_R=d\lambda^2-x_P-x_Q$. You should now see that the discrepancy resolves itself. More geometrically, note that the transformation is a stretch parallel to the $y$-axis and so preserves colinearity. $\endgroup$ Commented Jul 18, 2022 at 13:57
  • $\begingroup$ Oh I see, deriving the group addition law from 0 with the twist equation gives the extra coefficient for the slope in the expression for $x_3$. Yes, I had the sense of the stretch in the $y$-axis but couldn't make sense of it algebraically. Your answer clarifies everything. I''ll work the math out just to fixate it in my brain. Will also try to make sense of it deriving the group addition law when considering the equation for $E'$ that leaves the $y^2$ part unchanged. Thanks! $\endgroup$ Commented Jul 18, 2022 at 14:50
4
$\begingroup$

Over finite fields (at least of characteristic $>3$), this is correct.

As a reminder, a twist of an elliptic curve $E$ over a field $k$ is an elliptic curve $E'$ over the same field $k$ such that $E$ and $E'$ become isomorphic over some extension field $K/k$. A quadratic twist is the special case when the extension field $K$ is of degree $2$ over $k$.

Over a finite field $k$ (of characteristic $>3$), an elliptic curve always has exactly 6, 4 or 2 twists up to isomorphism, depending on whether its $j$-invariant is 0, 1728 or anything else respectively. Of those, exactly two are quadratic twists: namely the curve itself and the quadratic twist that you mentioned.

This can be proved in a fairly elementary way. Let's say for simplicity that $j\neq 0,1728$. You then know that both $E$ and $E'$ admit short Weierstrass forms $y^2 = x^3 + ax + b$ and $y^2 = x^3 + a'x + b'$ with $a,b,a',b'$ non zero. Those Weierstrass forms become isomorphic over the quadratic extension $k_2$ of $k$. This implies that there exists $u\in k_2^*$ such that $a' = u^4 a$ and $b' = u^6 b$. The quantity $u^2$ must be in $k$ since it's $u^6/u^4 = b/b'\cdot a'/a$, and if $u$ itself is in $k$, then $E$ and $E'$ are already isomorphic over $k$. Therefore the only non-trivial case is when $u=\sqrt{d}$ for some $d\in k^*$ which is not a square. It is easy to see that multiplying $d$ by a square doesn't change the isomorphism class, so there is only one non-trivial twist as required.

[There is also a high-brow version of the argument, that uses the classic Galois descent result that the set of ``objects $E$ over $k$'' that become isomorphic to $\bar{E}$ over $K$ is in bijection with the Galois cohomology space $H^1\big(\mathop{\textrm{Gal}}(K/k), \mathop{\textrm{Aut}}(\bar{E})\big)$. But the Galois set structure of the automorphism group of an elliptic curve over an algebraically closed field is well-known: it is just the Galois module $\mu_n$ of $n$-th roots of unity with $n=6,4,2$ depending on whether $j$ is 0, 1728 or something else (Silverman, Corollary III.10.2). Thus the set of twists of $E$ is in bijection with $H^1(\mathop{\textrm{Gal}}(\bar{k}/k),\mu_n) = (k^*)/(k^*)^n$, and the quadratic twists correspond to the $2$-torsion of that, so $(k^*)/(k^*)^2$. This holds over any field of characteristic $\neq 2,3$.]

Improve this answer
$\endgroup$
6
  • $\begingroup$ Awesome answer, very insightful. A few extra questions if you don't mind. 1) Why is the original curve considered a quadratic twist if it's trivially isomorphic to itself without needing any field extension? 2) When $j=0$, are there 2 quadratic twists, 2 quartic and 2 sextic? Do you have good references from where to learn about quartic and sextic twists? Thanks! $\endgroup$ Commented Jul 18, 2022 at 14:55
  • $\begingroup$ 1) It's a matter of convention. I'm sure you can find text that define "quadratic twist" to mean "non-trivial quadratic twist" and exclude the trivial case. In general though, it's more natural to include trivial cases. 2) When $j=0$, there is $E$ itself, 1 non-trivial quadratic twist, 2 non-trivial cubic twists and 2 non-trivial sextic twists (just as $\mathbb{Z}/6\mathbb{Z}$ contains 1 element of exact order 1, 1 of exact order 2, 2 of exact order 3 and 2 of exact order 6). When $j=1728$, there is $E$ itself, 1 non-trivial quadratic twist and 2 non-trivial quartic twist. $\endgroup$ Commented Jul 18, 2022 at 15:33
  • $\begingroup$ As for where to learn about quartic and sextic twists, they are frequently used in pairing-based cryptography so texts about that are a good place to look. For example Section 3.3.2 and 3.3.3 of the Guide to Pairing-Based Cryptography (El Mrabet and Joye, Eds.). $\endgroup$ Commented Jul 18, 2022 at 15:44
  • $\begingroup$ Thanks a lot! Will check that reference out. $\endgroup$ Commented Jul 18, 2022 at 15:51
  • $\begingroup$ one last question if you don't mind. Is the isomorphism a reality when both $E$ and $E'$ are defined over the extension? Ther reference you gave me (and others I've seen) describe the morphism as $E'(F_p) \to E(F_{p^d})$ which doesn't make too much sense to me. The co-domain should have many more points than the curve over the smaller field, right? I know this is useful because it's how you get simpler and faster computations in pairings by relying on the twist over the field of smaller size. $\endgroup$ Commented Jul 18, 2022 at 22:03

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.