0

Is there a way to solve for $x$ given $y$, in the equation $y^2 = x^3 + ax + b$, in the real number space (not finite field).

Or is the solution too difficult to achieve? I suspect the solution will require factoring a 3rd degree polynomial.

I'm trying to animate a dot going from top to bottom of the screen while following the curve. This will require inputing the $y$ component into some function, and getting the $x$ component in return, so that I can place the dot in the correct spot on the graph.

This question is not to be confused with the question asking about finding $x$ for the elliptic curve equation, in a finite field. I'm trying to solve in the real number space, not in the finite field.

Sal Rahman
  • 244
  • 2
    Sure, it's just a cubic. Cardano's method is the standard formula, if you're not trying to optimize for anything in particular. – anomaly Oct 12 '22 at 18:07
  • 1
    It is easy to solve in real numbers. You don't need to fix a $y$. If, say, $a$ and $b$ are positive, every positive real $x$ is possible, and $y$ is the square root of $x^3+ax+b$. For positive $b$, you always have the solution $(x,y)=(0,\pm \sqrt{b})$. – Dietrich Burde Oct 12 '22 at 18:08
  • 1
    https://en.wikipedia.org/wiki/Cubic_equation#Cardano's_formula may be used to get $x$ from a third degree polynomial in $x$ (such as $x^3 + ax + (b - y^2) = 0$) . However, there is not always a unique solution. (for the same reason $ax^2 + bx + c = 0$ doesn't always have a unique solution), – user3257842 Oct 12 '22 at 18:09
  • Cardano's formula is good, but it can sometimes be hard to figure out which root(s) is a real root, if I remember correct. – Thomas Andrews Oct 12 '22 at 18:11
  • An option might be, instead of continuously solving for one of the coordinates, to track the direction of the motion, and make differential changes (like in many other animations). The implicit function theorem tells us that from the point $(x,y)$ you can only go (a little way) to the direction of the vector $(2y, 3x^2+a)$. So you could, instead use update rules like $$x_{new}=x_{old}+(2y_{old}),\Delta t,\quad y_{new}=y_{old}+(3x_{old}^2+a)\Delta t.$$ Of course, even a small value of $\Delta t$ will gradually make the point drift away from the curve, so you need to periodically refine a bit. – Jyrki Lahtonen Oct 12 '22 at 19:09
  • Anyone willing to volunteer to mention "Cardano" as a possible solution below? I'd be happy to accept that as the answer, and give the lucky person the much deserved reputation bump (obviously bonus point if you can highlight the possible caveat to using Cardano's formula) – Sal Rahman Oct 12 '22 at 19:26

2 Answers2

2

It is perhaps easier to solve the equation $y^2=x^3+ax+b$ of an elliptic curve for given real $x$ (and not for given $y$), by taking $y=\pm\sqrt{x^3+ax+b}$ for those real $x$, which satisfy $x^3+ax+b\ge 0$.

Dietrich Burde
  • 130,978
  • Yes. From having talked to so many people, it seems solving for $y$ given a real $x$ is the easiest approach. Especially for elliptic curves – Sal Rahman Oct 12 '22 at 18:30
1

Consider the cubic equation $$ x^3 + \alpha x + (\beta-y^2) =0$$ The discriminant $$\Delta=-4 \alpha ^3-27 \left(y^2-\beta \right)^2$$ is always negative if $\alpha >0$. So, if this is the case, there is only one real root.

Using the hyperbolic method, this root is $$\color{blue}{x=-2 \sqrt{\frac{\alpha }{3}}\sinh \left(\frac{1}{3} \sinh ^{-1}\left(\frac 32 \sqrt{\frac3 {\alpha }}\,\,\frac{(\beta-y^2)}\alpha\right)\right)}$$

If $\alpha <0$ (still with $\Delta<0$), the solution is $$\color{blue}{x=-2 \sqrt{-\frac{\alpha }{3}}\,\,\frac{\left| \beta -y^2\right| }{\beta -y^2}\,\cosh \left(\frac{1}{3} \cosh ^{-1}\left(-\frac 32 \sqrt{-\frac3 {\alpha }} \,\,\frac{\left| \beta -y^2\right| }{\alpha }\right)\right)}$$

This is much better than using Cardano formula.

Claude Leibovici
  • 260,315