Order of twisted curve in pairings We are doing optimal Ate pairings using a Barreto-Naehrig curve, and I am trying to make sure that an observation I made generalizes.

We define $E$ as $y^2 = x^3 + 3$ and use the tower of extensions
\begin{equation}\begin{split}
        \mathbb{F}_{p^2} &amp;= \mathbb{F}_p[u] / (u^2 + 1) \\
        \mathbb{F}_{p^6} &amp;= \mathbb{F}_{p^2}[v] / (v^3 - (u+3)) \\
        \mathbb{F}_{p^{12}} &amp;= \mathbb{F}_{p^6}[w] / (w^2 - v)
\end{split}\end{equation}

and define the twisted curve $E'$ as $y^2 = x^3 + 3/(u+3)$.

Playing around in Sage, tweaking the BN parameters and playing with curves with different prime $p$ and order $r$, I found that the order of $E'$ was $r * (2p - r)$. But I haven't been able to find any confirmation that this is always true. Does anyone know if this is true in general, or if I just found a coincidence with my (very small) sample of curves?
Summary: no, this does not hold for all curves. It does hold for all Barreto-Naehrig curves, though; however, there are some subtleties.



First, some definitions. In order to define the question with all due precision, I must recall some known results.

Let $\mathbb{F}_q$ be a finite field of characteristic neither $2$ or $3$; that is, $q = p^f$ for some prime $p \geq 5$ and some integer $f \geq 1$. We consider curves $E$ over $\mathbb{F}_q$ with short Weierstraß equation $y^2 = x^3 + Ax + B$ for two constants $A$ and $B$ such that $4A^3 + 27B^2 \neq 0$ (if that last property is not fulfilled, there is a singular point with no tangent, hence which cannot be added to itself in a meaningful way, and the curve is not, stricto sensu, a curve).

Curve isomorphisms correspond to affine changes of variables; these are the transforms of the plane that map lines to lines, and therefore conserve point additions. It can be shown that the only possible changes of variables between two curves with short Weierstraß equations are $(x,y) \mapsto (e^2 x, e^3 y)$ for any $e \neq 0$ in $\mathbb{F}_q$. Such a change of variable transforms the curve equation into: $y^2 = x^3 + Ae^{-4}x + Be^{-6}$. We can thus to a large extent "normalize" either $A$ or $B$ to a small set of possible values.

The $j$-invariant of the curve is the field element:
$$ j = 1728 \frac{4A^3}{4A^3 + 27B^2} $$
Each element of $\mathbb{F}_q$ is a possible value for the $j$-invariant. When two curves have the same $j$-invariant, then either they are isomorphic to each other (in the sense explained above), or they are called twists of each other. When two curves are twists, then this means that they are isomorphic in a field extension; that is, there is a degree $k &gt; 1$ such that, lifted into $\mathbb{F}_{q^k}$, the two curve equations become two isomorphic definitions of the same curve (and this then holds also in the algebraic closure of $\mathbb{F}_q$). The twist is called quadratic if $k = 2$, cubic if $k = 3$, and so on.

In the general case, when the $j$-invariant is distinct from $0$ and from $1728$, the curve admits a single twist (up to isomorphism) and it is quadratic. Namely, let $d$ be a non-quadratic-residue in $\mathbb{F}_q$ (i.e. an element with no square root); an equation of the twist is then: $y^2 = x^3 + Ad^2x + Bd^3$. It can be seen that if we "invent" a square root $e$ of $d$, then this yields the isomorphism which was described above. $e$ does not exist, by construction, in $\mathbb{F}_q$; therefore, adjoining $e$ to $\mathbb{F}_q$ yields $\mathbb{F}_{q^2}$, a degree-2 extension (in the usual definition of field extensions with polynomials, we are using the irreducible polynomial $X^2 - d$, and call $e$ one of its roots in the field extension).

It can be shown that if the curve $E(\mathbb{F}_q)$ has cardinal $q+1-t$ (with $t$ being the trace of Frobenius, bounded by Hasse's theorem: $t^2 \leq 4q$), then the twist has cardinal $q+1+t$, i.e. the trace is simply negated. The elementary proof consists in enumerating elements $x$ in $\mathbb{F}_q$:


If $x$ is such that $x^3 + Ax + B$ is the square of $y \neq 0$, then there are two points $(x,y)$ and $(x,-y)$ on $E$. But then, $(dx)^3 + Ad^2(dx) + Bd^3 = d^3 y^2$, and since $d$ is not a square in $\mathbb{F}_q$, this last value is not a square, and there is no point $(dx,y')$ on the twist $E'$.
Conversely, if $x^3 + Ax + B$ is not a square in $\mathbb{F}_q$, then there is no point $(x,y)$ on $E$, but there will be two points $(dx,y')$ on $E'$.
If $x^3 + Ax + B = 0$, then $(x,0)$ is a point on $E$, and $(dx,0)$ is a point on $E'$.


Thus, by enumerating the $q$ possible values of $x$, we obtain always two points: either two on $E$, or two on $E'$, or one of each of $E$ and $E'$. This covers all points of $E$ and $E'$ except the point-at-infinity, which does not have coordinates per se, and is part of both curves. Therefore, $\#E + \#E' = 2q + 2$, from which the result is obtained.

Note that, from the $j$-invariant, a matching curve equation is obtained as:
$$ y^2 = x^3 + \frac{3j}{1728 - j} x + \frac{2j}{1728 - j} $$

If the $j$-invariant is zero, then this corresponds to curves of equation $y^2 = x^3 + B$ (i.e. $A = 0$). There are only six curves with such an equation, up to isomorphisms (i.e. there are exactly six isomorphism classes); moreover, they are all twists of each other. Some of these will be quadratic twists, some will be cubic twists, and some will be sextic twists.

If $q = 2 \bmod 3$ (this may happen only if the characteristic $p$ is itself equal to $2$ modulo $3$, and $q = p^f$ for an odd integer $f$), then every element of $\mathbb{F}_q$ has a single cube root; therefore, for every $y \in \mathbb{F}_q$, there is a single $x$ such that $x^3 = y^2 - B$. It follows that the curve order is $q + 1$, and the curve is supersingular, and the embedding degree of the curve is $2$, and you don't want that for your pairings. Supersingular curves have a bunch of special properties, which I won't detail here.

I now suppose that $q = 1 \bmod 3$. Since $q$ is odd (it is a power of the characteristic, which we supposed was not equal to $2$, and is prime, and therefore odd), it follows that $q = 1 \bmod 6$. This implies that there are non-trivial sixth roots of unity, and that there are elements $\xi$ such that $X^6 - \xi$ is irreducible (there's a short proof of it given in the Barreto-Naehrig article, on page 6). We obtain all curve classes by enumerating the equations:
$$ y^2 = x^3 + \frac{B}{\xi^i} $$
for all $i$ from $0$ to $5$.

With $\xi^0$, we have the curve $E$ itself. With $\xi^3$, we get a quadratic twist of $E$. With $\xi^2$ and $\xi^4$, we obtain two cubic twists of $E$. With $\xi$ and $\xi^5$, we get two sextic twists of $E$.

Now for the group orders. When a curve has $j$-invariant zero, then its group order can only take six values (corresponding to the six isomorphism classes). Consider the integer $4q - t^2$: as indicated above, by Hasse's theorem, this integer is nonnegative. You can make it square-free by removing all prime factors with an even exponent; i.e. you can write:
$$ 4q - t^2 = Dv^2 $$
for integers $D$ and $v$, where $D$ is square-free (i.e. there is no prime integer $z$ such that $z^2$ divides $D$). By unicity of the factorization of integers, $D$ is uniquely defined. For curves of $j$-invariant zero, it so happens that $D = 3$, always; and this also works in the other way: if $D = 3$, then the curve MUST have $j$-invariant zero (this comes from complex multiplication theory, which is, indeed, rather complicated). From the value $v$, we can obtain the orders of the twists of curve $E$. We recall that $\#E(\mathbb{F}_q) = q + 1 - t$; then:


Quadratic twists of $E$ have order $q + 1 + t$.
Cubic twists of $E$ have order $q + 1 - (3v-t)/2$ or $q + 1 - (-3v-t)/2$.
Sextic twists of $E$ have order $q + 1 - (-3v+t)/2$ or $q + 1 - (3v+t)/2$.


For a demonstration and pointers, see The Eta Pairing Revisited, section 4.

The third case is when the $j$-invariant is equal to $1728$. This corresponds to curve equations $y^2 = x^3 + Ax$, i.e. $B = 0$. If $q = 3 \bmod 4$, then this defines a supersingular curve. If $q = 1 \bmod 4$, then you get four isomorphism classes, all twist of each other; such a curve accepts one quadratic twist and two quartic twists (extension degree 4). I won't detail that one, but see the Hess-Smart-Vercauteren article for details.

Another useful result is that, given a curve $E$ defined over field $\mathbb{F}_q$, with order $\#E(\mathbb{F}_q) = q + 1 - t$, the order of $E$ over field extensions can be computed as follows:
$$ \#E(\mathbb{F}_{q^n} = q^n + 1 - (\alpha^n + \overline{\alpha}^n) $$
for all integers $n \geq 1$, where $\alpha$ and $\overline{\alpha}$ are the two (complex) roots of polynomial $X^2 - tX + q$. There is a nice recurrence relation:


$\alpha^0 + \overline{\alpha}^0 = 2$
$\alpha^1 + \overline{\alpha}^1 = t$
$\alpha^{n+1} + \overline{\alpha}^{n+1} = t(\alpha^n + \overline{\alpha}^n) - q(\alpha^{n-1} + \overline{\alpha}^{n-1})$


In particular, $\alpha^2 + \overline{\alpha}^2 = t^2 - 2q$



All of this being stated, let's see your specific problem.

You have a prime $p = 1 \bmod 3$. A curve is defined over $E(\mathbb{F}_p)$, with equation $y^2 = x^3 + B$; this is a curve of $j$-invariant zero. Its order is denoted $r$. This curve has a trace $s$, which is such that $r = p + 1 - s$. In BN curves, $r$ is also prime, but this does not matter here.

You then lift the curve into $\mathbb{F}_{p^2}$. I write $q = p^2$: you are interested in twists of $E$ as defined over $\mathbb{F}_q$, not twists of $E$ as defined over $\mathbb{F}_p$. It is important to be precise about such things; this is the reason why I used $q$ and not $p$ in all the treatment above.

With the results above, you can compute:
$$ \#E(\mathbb{F}_q) = q + 1 - (s^2 - 2p) $$
i.e. the trace of the curve over $\mathbb{F}_q$ is $t = s^2 - 2p$.

Since this is a curve of $j$-invariant zero, it admits 5 twists, two of which being sextic, with orders:
\begin{eqnarray*}
    o_1 &amp;=&amp; q + 1 - \frac{3v + t}{2} \\
    o_2 &amp;=&amp; q + 1 - \frac{-3v + t}{2} \\
\end{eqnarray*}
where $v$ is such that $4q - t^2 = 3v^2$.

The question is then: is it guaranteed that one of these two sextic twists has order exactly $r(2p-r) = (p+1-s)(p-1+s)$?

The answer is: no. Here is a counterexample:

Let $p = 31$. The curve $y^2 = x^3 + 3$ has order $r = 43$, i.e. its trace is $s = -11$. The quadratic extension is $q = 961$; over $\mathbb{F}_q$, the curve $E$ has trace $t = s^2 - 2p = 59$. We note that $4q - t^2 = 363 = 3(11^2)$, thus $v = 11$. The orders of the two sextic twists are then $o_1 = 916$ and $o_2 = 949$. However, $(p+1-s)(p-1+s) = 817$, which is distinct from both $o_1$ and $o_2$.

However, for BN curves, this works. Recall that a BN curve is parameterized by an integer $u$, and:


$p = 36u^4 + 36u^3 + 24u^2 + 6u + 1$
$s = 6u^2 + 1$


The integer $u$ is chosen so that $p$ is prime, and the curve order $r = p+1-s$ is also prime. Under such conditions, one can notice that:
$$ 4p - s^2 = 3(6u^2 + 4u + 1)^2 $$
Hence $s$ is the trace for some curve over $\mathbb{F}_p$ with $j$-invariant zero. We can then lift that curve into $\mathbb{F}_q$ with $q = p^2$, and that one will have two sextic twists.

This choice of $p$ and $s$ implies that $r$ divides $p^{12}-1$, which means that the embedding degree (the crucial property for defining pairings) will be at most $12$, hence the curve will be "pairing-friendly".

With these parameters, you get:


$q = p^2$
$t = -36u^4 - 72u^3 - 36u^2 - 12u - 1$
$4q - t^2 = 3v^2$ with $v = (6u^2+4u+1)(6u^2+1)$


And thus, the two sextic twist orders are:
\begin{eqnarray*}
    o_1 &amp;=&amp; 1296u^8 + 2592u^7 + 3024u^6 + 2160u^5 + 1044u^4 + 360u^3 + 84u^2 + 12u + 1 \\
    o_2 &amp;=&amp; 1296u^8 + 2592u^7 + 3024u^6 + 2160u^5 + 1152u^4 + 432u^3 + 120u^2 + 24u + 4 \\
\end{eqnarray*}

If you compute the expression for $(p+1-s)(p-1+s)$, you will find that you get exactly the same polynomial as $o_1$. Therefore, for any BN curve, it is guaranteed that one of the sextic twists $E'$ of $E$ (over $\mathbb{F}_q$) will have order $(p+1-s)(p-1+s) = r(2p-r)$.

Note: there still are two sextic twists. When you choose your $\xi$ such that $X^6-\xi$ is irreducible over $\mathbb{F}_q$, you might be unlucky and obtain the wrong one. The other twist can be obtained by using $\xi^5$ instead (or you could try again with another $\xi$, since you want one that makes computations easiest to do).