有限域上椭圆曲线任意的点 P 和 Q 都存在以 P 为底 Q 的椭圆曲线离散对数

问题：

设 E 为有限域 F 上的椭圆曲线，P、Q ∈ E(F) 且 P ≠ Q，证明：存在整数 k，使得 Q = kP。

证明：

由于 P ≠ Q，因此 P 和 Q 是 E(F) 中的不同点。设 E 的方程为 y² = x³ + ax + b，P 的坐标为 (x1, y1)，Q 的坐标为 (x2, y2)。

如果 x1 ≠ x2，则直线 L 通过 P 和 Q，其方程为：

y − y1 = k(x − x1) (1)

其中 k = (y2 − y1)/(x2 − x1)。将 L 的方程代入 E 的方程，得到：

(x − x1)³ + a(x − x1) + b − (y − y1)² = 0

将 y 用 (1) 代入上式，得到：

(x − x1)³ + a(x − x1) + b − [k(x − x1) + y1]² = 0

展开后整理得到：

x³ − 3x1x² + [3x1² − a]x + [b − y1² + 2ky1x1 − k²x1²] = 0

由于 P 和 Q 都在曲线上，因此上式的另一个根必然是 x2，即：

x³ − 3x1x² + [3x1² − a]x + [b − y1² + 2ky1x1 − k²x1²] = (x − x2)(x − x1)²

将 x2 代入上式，得到：

0 = (x2 − x1)³ + a(x2 − x1) + b − (y2 − y1)²

将 k = (y2 − y1)/(x2 − x1) 代入上式，得到：

0 = (x2 − x1)³ + a(x2 − x1) + b − [(y2 − y1)/(x2 − x1)]²

移项整理得到：

(x2 − x1)³ + a(x2 − x1) + b − [(y2 − y1)/(x2 − x1)]² = 0

上式可以写成一个三次不可约多项式的形式，因此它有一个根在 F 上，设为 x0。

由于 F 是有限域，因此 F 中的元素个数为有限个，设为 N。则曲线 E(F) 中的点个数为：

|E(F)| = N + 1 − t

其中 t 是 E(F) 中的点的数目，也是 x³ + ax + b 在 F 上的根的个数。由于 x³ + ax + b 在 F 上是不可约的，因此 t ∈ {1, 3}。

当 t = 1 时，|E(F)| = N + 1，因此 E(F) 中的每个点都可以表示成 kP 的形式，其中 k ∈ {0, 1, …, N}。

当 t = 3 时，|E(F)| = N − 1，因此 E(F) 中的每个点都可以表示成 kP 的形式，其中 k ∈ {0, 1, …, N − 2}。此时，假设 Q = kP，则有 k ∈ {0, 1, …, N − 2}。因此，我们只需要枚举 k 的值，找到一个满足条件的 k 即可。

综上所述，对于任意的 P、Q ∈ E(F) 且 P ≠ Q，都存在整数 k，使得 Q = kP