0

Currently I was trying to solve a problem with the condition below:

1. giving an elliptic curve y^2 = x^3 + ax + b
2. the user will input a, b and two points that exactly on the curve.

To put it simply, what I really need to do is make a secant line of the graph with the two points P and Q and try to check that if there is any point of intersection existing. If it exists, get the x and y of this point. I'm so struggled to solve this problem. Could someone give me some hints?

3
  • Hi and welcome to stackoverflow! Please refer to How to create a Minimal, Complete, and Verifiable example. when asking questions.
    – Enfyve
    Nov 10, 2018 at 7:34
  • 2
    You didn't mention it - hence, my hint: First of all, search for a mathematical solution. Once you have a mathematical idea, think about how to implement it in C++. Nov 10, 2018 at 7:53
  • The formulas for this are well-documented in a number of places; I'd suggested googling for "elliptic curve addition". Nov 11, 2018 at 8:39

1 Answer 1

0

I'd homogenize this to x^3 + axz^2 + bz^3 - y^2z = 0 and points P = [Px : Py : Pz] and Q = [Qx : Qy : Qz]. Then any point R = λP + μQ with (λ, μ) ≠ (0, 0) lies on the line spanned by P and Q. If you wanted to avoid homogenizations, you'd require λ+μ=1 but that usually leads to divisions I'd rather avoid until the very end.

Plug the resulting coordinates of R into the homogenized equation of the elliptic curve, and you obtain a homogeneous cubic equation in λ and μ, i.e. something like

αλ³ + βλ²μ + γλμ² + δμ³ = 0

with the α, β, γ and δ depending on your a, b, P, Q. For μ=0 you get a coordinate vector which is a multiple of P, and as homogeneous coordinates identify multiples, you get point P itself, which lies on the curve. So μ=0 must satisfy the equation, hence you know α=0 even before you compute it. Likewise λ=0 represents Q so δ=0 if that point lies on the curve. You are left with

(βλ + γμ)λμ = 0

The trailing two factors encode the two known intersections I just mentioned. The parenthesis is the third intersection, the one you need. Now simply pick λ=γ and μ=−β to obtain a simple expression for the third point of intersection.

If you want to dehomogenize at the end, simply divide the first two coordinates of the resulting homogeneous coordinate vector by the third.

If I didn't mess up my sympy computation, you have

β = 3*Px^2*Qx + 2*Px*Pz*Qz*a - Py^2*Qz - 2*Py*Pz*Qy + Pz^2*Qx*a + 3*Pz^2*Qz*b
γ = 3*Px*Qx^2 + 2*Pz*Qx*Qz*a - Pz*Qy^2 - 2*Py*Qy*Qz + Px*Qz^2*a + 3*Pz*Qz^2*b

Which is expectedly very symmetric in P and Q. So essentially you just need a single function, and then you get β=f(P,Q) and γ=f(Q,P).

In C++ and with the whole homogenization / dehomogenization in place:

inline double f(double Px, double Py, double Qx, double Qy, double a, double b) {
  return 3*Px*Px*Qx + 2*Px*a - Py*Py - 2*Py*Qy + Qx*a + 3*b;
}

std::pair<double, double> third_intersection(double Px, double Py, double Qx, double Qy, double a, double b) {
  double beta = f(Px, Py, Qx, Qy, a, b);
  double gamma = f(Qx, Qy, Px, Py, a, b);
  double denominator = gamma - beta;  // Might be zero if line PQ is an asymptote!
  double x = (gamma*Px - beta*Qx) / denominator;
  double y = (gamma*Py - beta*Qy) / denominator;
  return std::make_pair(x, y);
}

Not the answer you're looking for? Browse other questions tagged or ask your own question.