Diophantine equations and elliptic curves
在上一篇 post 中,我们介绍了在椭圆曲线上的 weil pairing 和 tate pairing。在这一篇中我们考虑椭圆曲线在丢番图方程上的一些应用。
问题零
我们在初中数学中学过,直角三角形满足勾股定理,设两个直角边为
那么满足三边均为整数的直角三角形有无数个吗?
这便是一个丢番图方程的经典例子。一般而言,丢番图方程(Diophantine equations)是有一个或者几个变量的整系数方程,它们的求解仅仅在整数范围内进行。
我们学到的最简单的方程应该是线性丢番图方程,即形如:
的方程,其中
为整数, 为未知数。该方程可以使用扩展欧几里得算法来解决。
当然,上面这道题并不需要用到 elliptic curves 的内容来进行分析(所以才叫“问题零”)。
下面说一下问题零的解答,注意到:
这个其实是初中数学老师的某一堂课注意到的。
因此满足三边长度均为整数的直角三角形有无数个,令
例如:
问题一
我们在小学数学时就学过直角三角形的面积为
那么问题是,可以找到面积
这道题相当于我们有两个条件的 diophantine equation:
要求其有理数解。如果我们如法炮制用
的有理数解,方程的次数变成了
我们注意到:
这个是书上说注意到的,这个应该比上一个显然。
因此我们设
只要找到一组解
都是有理数的平方,就可以找到对应满足条件的 .
如果
来寻找里面 non-trivial 的有理点。
找到第一个解
我们首先可以找到三个有理点
通过简单的搜索,我们可以找到一个非平凡的有理点
但我们可以从这个点出发做切线,来与
我们尝试做点
代入点
将该函数与
展开后可得常数项为
我们得到了对应的
因此:
可以发现
综上,我们得到了一个解
证明解有无穷多个
下一个问题是,存在无数个这样的三元组
因为
因此得到下一个三元组
我们讨论类似这样的一般方程:
中有非平凡有理数点
首先我们求出切线方程:
根据韦达定理,可得:
因为
注意到:
这个是 deepseek R1 注意到的,我注意力不行(
因此
即
我们可以按照这种迭代方法生成
问题二
这是我在初中时同学给我的一道钓鱼题:
我当时试了一下,发现这个问题能解决的人数占比应该没有 5%。事后同学告诉了我那三个巨长的答案,于是我意识到了一些数论问题的魅力:
看上去十分简单的问题陈述,其答案和解法却非常复杂。
化为 Weierstrass 形式
首先这个方程是齐次的,这意味着只要我们找到一组解
按照问题一的思路,我们首先应该考虑如何将题目所给的方程:
转化为椭圆曲线的形式——这个可比问题一的难度大多了。
首先尝试通分:
然后我们需要用
可以通过穷举找到
然后代入
令
是可逆矩阵。一个简单的做法是令点
例如取
令
令
两边同时除以
这两者便是参考文献六一开始提到的投影形式和仿射形式。
这个时候我们尝试将
然后就能得到
同样我们也可以算出其逆变换(这里省略了自由变量
找到一组正整数解
尝试暴力穷举寻找新的方程的整数解,可以通过脚本枚举
1 | (-39, 52) |
把解带回
1 | (x, y) = (-39, 52) -> (a, b, c) = (-13, 52, 143) [Valid] |
其中第五、六行就是参考资料四中使用的特殊解。
但此时对应的
这里的过程就比较简单了,只需暴力循环无脑判断就行。这里我也懒得造轮子,直接让 GPT 写 sagemath 的椭圆曲线库搞定:
1 | E = EllipticCurve(QQ, [1, 69, 0, 1365, 8281]) # [a1, a2, a3, a4, a6] |
与参考资料四相同,当迭代次数
iteration=9
时,输出为:
同时乘他们最小公倍数即可得到正整数解:
问题三
有好事者在问题二梗图的启发下,把一个看上去更简单的问题搞成了这种人畜无害的形式:
这就是著名的“三立方和问题”,即求:
的整数解
而图片中的问题,即
由于这个方程不是齐次方程,所以问题二的倍点方法又行不通了。Andrew
发的论文思路是通过降低暴力枚举的时间复杂度(从
的算法
首先考虑问题的弱化版——两立方和问题,一个比较简单的结论是对于质数
有整数解的
因为
,因为 为质数,故:
先考虑右式,只有
满足条件。对应的 为 . 再考虑左式,令
,右边就成了 了(当然得必须是质数)。
我们尝试将
是个标准的一元二次方程。则
回到先前的三立方和问题,可以将
然后应用之前的两立方和问题判断算法,只需枚举
转化为椭圆曲线
假设
这里
则
这里
对于给定的搜索范围
对于指定的整数
使得对应的整点恰好是上式的整数解,具体的映射为
于是这个问题又转化为了在
这种代数变换对于较小的
Booker 使用了代数软件 Magma 的椭圆曲线求整点功能,验证了在
但是椭圆曲线的参数
进一步优化
回到上一节,为了求得满足
的
- 为了计算满足
的 ,我们需要 的质因数分解。 - 可能的
对有 个。
论文除了使用椭圆曲线排除了一部分整数
首先说一下 batch inversion,给定
- 计算
。从 计算到 只需 次模乘法运算。 - 使用扩展欧几里得计算
,时间复杂度 。 - 当
时,计算 ,随后计算 。 - 令
,对于 进行同样操作。
于是计算的时间复杂度从
回到瓶颈一,这里将
- 如果
,根只有一个,则 ,使用快速幂可以搞定,时间复杂度 。 - 如果
:- 令
。 - 迭代计算
,直到 ,当且仅当 时立方根存在。 - 任取
,使得 的阶为 ,计算 ,则 , 是 的立方根。 - 取
满足 ,则 . 另外两根为 .
- 令
然后使用hensel
提升法扩展到
如果先前用 batch inversion
的时候把逆元存下来,并且使用各个质数的“线性组合”来列举
考虑瓶颈二,令
选取
如果事先计算
除了复杂度的降低外,Andrew 在后续工作 Sums of three cubes
提到针对特定
在具体实现方面,论文使用了 intel intrinsics
并利用超级计算机并行(
参考资料
https://baike.baidu.com/item/%E4%B8%A2%E7%95%AA%E5%9B%BE%E6%96%B9%E7%A8%8B/5466939
https://zhuanlan.zhihu.com/p/354425450
Elliptic curves: number theory and cryptography
https://zhuanlan.zhihu.com/p/33853851
https://www.zhihu.com/question/267427508/answer/323883323
Transforming a general cubic elliptic curve equation to Weierstrass form
An unusual cubic representation problem
Cracking the problem with 33
Sums of three cubes (Andrew Sutherland)
https://zh.wikipedia.org/wiki/%E4%BA%A8%E6%B3%BD%E5%B0%94%E5%BC%95%E7%90%86