# Checking if point is on EC twist

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

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: $$$$\beta^3({y_0}^2 - {x_0}^3) - \beta Ax - B = 0.$$$$ 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$$: $$$$\beta^3 ({y_0}^2 - {x_0}^3) + 3 \beta x_0 - 60 = 0.$$$$ With our favourite computer algebra software, we find $$\beta = 67$$. Then the equation of $$E'$$ is $$$$y^2 = x^3 + 74x + 97.$$$$

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