带割线的椭圆曲线

Question

目前我正在尝试解决以下情况的问题：

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.

简而言之，我真正需要做的是用两点P和Q做一条图形的割线，并尝试检查是否存在任何交点。如果存在，则获取该点的 x 和 y。我很难解决这个问题。有人可以给我一些提示吗？

Answer 1

我将其统一化为 x^3 + axz^2 + bz^3 - y^2z = 0 并指向 P = [Px : Py : Pz] 和 Q = [Qx : Qy : Qz]。然后任何点 R = λP + μQ 且 (λ, μ) ≠ (0, 0) 位于 P 和 Q 跨越的线上。如果你想避免均质化，你需要 λ+μ=1 但这通常会导致到最后我宁愿避免分裂。

将得到的R坐标代入椭圆曲线的齐次方程，得到λ和μ的齐次三次方程，即

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

α、β、γ 和 δ 取决于你的 a、b、P、Q。对于 μ=0，你得到一个坐标向量，它是 P 的倍数，并且齐次坐标识别倍数，你得到点 P 本身，位于曲线上。所以 μ=0 必须满足方程，因此您甚至在计算之前就知道 α=0。同样，λ=0 表示 Q，因此如果该点位于曲线上，则 δ=0。你还剩下

(βλ + γμ)λμ = 0

后面的两个因子编码了我刚才提到的两个已知交叉点。括号是第三个交集，您需要的那个。现在简单地选择 λ=γ 和 μ=−β 以获得第三个交点的简单表达式。

如果想在最后去均质化，只需将生成的齐次坐标向量的前两个坐标除以第三个即可。

如果我没有搞砸我的 sympy 计算，你有

β = 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

这在 P 和 Q 中预计是非常对称的。所以基本上你只需要一个函数，然后你得到 β=f(P,Q) 和 γ=f(Q,P)。

在 C++ 中以及整个同质化/去同质化到位：

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);
}

带割线的椭圆曲线

Elliptic Curve with a secant line

c++

math

geometry

elliptic-curve