2
$\begingroup$

Given a short Weierstrass elliptic curve $C$ over $F_p$ and a point $(x, y)$, it is easy to verify that $(x, y)$ either satisfies the curve equation (on-curve) or does not (off-curve).

In the case that it is off-curve, is there an efficient way to test if $(x, y)$ is on a quadratic twist of the curve? I can easily generate domain parameters $a, b$ of a twisted curve $C'$, but unless I have the correct coefficients, $(x, y)$ might not satisfy that particular curve equation $C'$ even though $(x, y)$ are on a twist of $C$.

$\endgroup$
4
$\begingroup$

Let $E$ be an elliptic curve over $\mathbf F_p$ given by the equation $y^2 = x^3 + Ax + B$. Then a quadratic twist $E'$ of $E$ is given by the equation $\beta y^2 = x^3 + Ax + B$ where $\beta$ is not a square.

Now you have a point $(x_0, y_0)$ you suppose is not on $E'$. Then to make it on a twist, you need to find $\beta$ such that $\beta {y_0}^2 = {x_0}^3 + Ax_0 + B$. If $\beta$ is not a square, then you found a quadratic twist of the curve with $(x_0, y_0)$ belonging on it.

Now, if you want $E'$ to have a short Weierstrass form, you can instead look for a non-square $\beta$ such that the following equation is satisfied: \begin{equation} \beta^3({y_0}^2 - {x_0}^3) - \beta Ax - B = 0. \end{equation} Then, $E'$ is given by the equation $y^2 = x^3 + A'x + B'$ where $A'=\frac{A}{\beta^2}$ and $B'=\frac{B}{\beta^3}$.

Example

Let $E$ the elliptic curve of equation $y^2 = x^3 - 3x + 60$ over the field $\mathbf F_{101}$ and the point $P=(5,17)$ that is not on the curve.

We will try to find the short Weierstrass equation of the twist $E'$ where $P$ lies on it.

We take the above equation and solve for $\beta$: \begin{equation} \beta^3 ({y_0}^2 - {x_0}^3) + 3 \beta x_0 - 60 = 0. \end{equation} With our favourite computer algebra software, we find $\beta = 67$. Then the equation of $E'$ is \begin{equation} y^2 = x^3 + 74x + 97. \end{equation}

Let's check everything:

sage: p = 101
sage: E = EllipticCurve(GF(p), [-3, 60])
sage: q = E.cardinality()
sage: q
113
sage: x_0, y_0 = 5, 17
sage: E.is_on_curve(x_0,y_0)
False
sage: R.<X> = GF(p)[]
sage: f = X^3*(y_0^2 - x_0^3) + 3*X*x_0 - 60
sage: f.roots()
[(67, 1)]
sage: F(67).is_square()
False
sage: EE = EllipticCurve(GF(p), [-3/beta^2,60/beta^3])
sage: qq = EE.cardinality() 
sage: qq
91
sage: sage: EE.is_on_curve(x_0,y_0)
True
sage: q + qq == 2*(p + 1)
True

The last instructions check the relation between the cardinality of $E$ and its quadratic twist.

Final remark.

This shows how to construct a specific quadratic twist having a specific point, but if you do this with another random point, not on $E$, then it might not be on the previously constructed twist $E'$.

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