椭圆曲线

求解某个方程的整数解或是正整数解, 这是个古老而又困难的数论问题, 这类问题被称为丢番图方程.

通过某种巧妙地构造发现, 作代换

$$\begin{cases} x=-\dfrac{4 (n+3) (a+b+2 c)}{n (a+b)+2 a+b-c}\\ y=\dfrac{4 \left(2 n^2+11 n+15\right) (a-b)}{n (a+b)+2 a+b-c} \end{cases}$$

原式可以转换为

$$y^2 = x \bigl(x^2 + (4n(n+3)-3)x + 32(n+3)\bigr) =: x(x^2 + Ax + B)$$

于是问题划归为求解椭圆曲线方程的解, 消掉一个自由度, 求解整数解变求解有理数解.

$$y^2=x \left(x^2+109 x+224\right);\mathtt{where}\ x,y\in\mathbb{Q/\{0\}}$$

椭圆曲线上的所有有理点都能通过有限的几个生成元得到

椭圆曲线的生成元(类似线性代数的基底)个数取决于椭圆曲线的阶(类似线性代数的维度).

椭圆曲线上的加法定义为

因为椭圆曲线的加法几乎是随机的, 所以期望某次相加后符合要求

椭圆曲线上的乘法当然可以通过慢慢加得到, 但是这样是线性复杂度, 比较好的方案是二进制分解, 用类似快速幂的方法计算, 这样能降低到对数复杂度.

$$9=1001_2=8+P;8=4+4;4=2+2;2=P+P$$

这样一共是4次运算, 乘数大的时候非常划算.

但是你要是要求其逆运算, 求其对数, 这个就非常困难了, 你只能线性的一个一个去加看看符不符合, 这几乎是不可能找到原来的乘数的.

这是椭圆曲线加密(ECC)的数学基础, 非常的靠谱. 当然前提是没有数学武器降维打击, 有多种高深的数学工具可以或多或少加速这个过程.

密码学界也在着手更加高级(艰深)的加密手段, 我能做的只有信任... 毕竟...反正我也看不懂了...