Vélu 公式学习材料

椭圆曲线同源计算发展史

形成与发展期 (1971-1998)

1971

Vélu 公式

首次提出椭圆曲线同源显式计算方法

→

Ref: Vélu, J. Isogenies between elliptic curves
辅助理解材料 MIT 18.783 Lecture 4

1972

Stark 方法

发展了复乘理论与模多项式

→

Ref: Stark, H. M. Class-Numbers of Complex Quadratic Fields

1990

Elkies 公式

同源的有理分式形式，SEA算法核心

→

SEA 算法在数点上的关键突破。通过寻找模多项式的根来确定同源的核多项式，从而以有理分式的高效形式计算同源，极大地加速了大特征有限域上的标量乘法与数点效率。

Ref: Elkies, N. D. Elliptic and modular curves over finite fields and related computational issues

1994

Couveignes 算法

小特征域椭圆曲线的同源计算

→

深度介绍：解决了 Elkies 方法在小特征域上因形式导数为零而失效的困境。该算法巧妙利用了 $p$-挠子群 ($p$-torsion) 上的形式群来进行同源计算。

Ref: Couveignes, J. M. [HAL]

1996

Lercier 算法

特征 2 域椭圆曲线同源计算

→

深度介绍：针对特征 2 的有限域 $\mathbb{F}_{2^n}$ 构建了基于形式代数的专用算法。由于特征 2 域在硬件实现中的高效性，此算法对早期基于硬件的椭圆曲线密码学极其重要。

Ref: Lercier, R. [DOI]

1996

Couveignes 改进

插值法计算同源

→

深度介绍：提出基于有理插值的方法计算同源代数表达，避免了部分复杂的塔式代数扩张计算，完善了小特征域同源工具链，降低了常数时间开销。

Ref: Couveignes, J. M. [DOI]

1998

推广 Elkies 公式

进一步扩展适用范围与效率

→

深度介绍：将 Elkies 方法推广到更一般的同源次数 $\ell$ 及更广泛的椭圆曲线方程形式，大幅提高了 SEA 算法的通用性。

Ref: Elkies, N. D. [arXiv]

巩固期 (2008-2016)

2008

Lercier 优化

$p$-进数优化小特征上的计算

→

深度介绍：引入 $p$-进数解析技巧，将小特征域上的同源核计算提升到 $p$-进精度，克服了特征 $p$ 带来的除法失效问题，显著降低渐进复杂度。

Ref: Lercier, R., et al. [DOI]

2008

Bostan 优化

优化 Elkies 方法的计算复杂度

→

深度介绍：利用快速傅里叶变换 (FFT) 对 Elkies 方法的底层多项式操作进行优化，将时间复杂度逼近拟线性界 $\tilde{O}(\ell)$。

Ref: Bostan, A., et al. [DOI]

2010~2016

Luca De Feo 的奠基性工作

完成向现代密码学应用跨越的关键转折，为同源密码学奠基

→

里程碑深度介绍：Luca De Feo 及其合作者系统探讨了普通与超奇异曲线在不同特征下的同源计算复杂度，提出了在超奇异同源图中进行随机游走的哈希函数与密钥交换协议，直接催生了 SIDH，标志着抗量子同源密码学时代的正式开启。

Ref: De Feo, L. [arXiv]

密码驱动发展期 (2017-2022)

2017

Montgomery 曲线同源

系统提出各项底层计算细节

→

深度介绍：针对 SIDH 协议需求，彻底优化了 Montgomery 曲线上仅使用投影坐标运算的底层公式，极大地减少了有限域上的乘法和平方次数，成为现代同源密码代码库的基石。

Ref: Costello, C., et al. [ePrint]

2020

$\sqrt{\text{élu}}$ 公式

大次数同源，结式+BSGS，次线性

→

深度介绍：面向 CSIDH 等需大素数次同源的场景。通过将求值问题转化为多项式多点求值问题（运用结式与 BSGS），将 Vélu 公式的复杂度从 $O(\ell)$ 降至次线性 $\tilde{O}(\sqrt{\ell})$。

Ref: Bernstein, D. J., et al. [ePrint]

2020

根式 Vélu (Radical)

小次数同源，去随机选点，Tate形式

→

深度介绍：对于密集的同源链，提出利用 Tate 范式和除多项式直接写出目标曲线系数，彻底去除了以往“随机选点求核”的性能瓶颈，实现常数时间计算优化。

Ref: Castryck, W., et al. [ePrint]

2022

$\sqrt[N]{\text{élu}}$ 公式

奇数次同源，去随机选点，Tate配对

→

深度介绍：根式 Vélu 的泛化版本。结合双线性 Tate 配对等工具，将“去随机选点”优势推广到任意奇数阶同源，实现通用且极其高效的代数结构重构。

Ref: On N-th root isogenies [ePrint]

2022

高维同源攻击

SIDH 的破灭，多项式时间破解

→

深度介绍：Castryck-Decru 和 Maino-Martindale 等人突破性地利用 Kani 定理与高维阿贝尔簇（Abelian Surfaces）上的同源计算，将 1 维同源问题提升到 2 维及以上，在多项式时间内破解了 SIDH。

Ref: Castryck, W., Decru, T. [ePrint]

2022

Damien Robert 算法

多项式时间计算任意次数同源

→

深度介绍：受 SIDH 攻击启发，Damien Robert 提出通过高维阿贝尔簇，在时间复杂度仅为 $\tilde{O}(\log \ell)$（即关于次数 $\ell$ 为多项式时间）内计算并评估任意 $\ell$ 次同源。这是彻底颠覆 Vélu 体系的理论天花板！

Ref: Robert, D. [ePrint]

×

• Vélu 公式原始论文：Isogenies between elliptic curves

• 优秀的辅助理解材料：MIT 18.783 Lecture 4

• 一个简单的短综述，总结了2017年之前的发展，一直到 Couveignes 算法：Calcul d’isogénies entre courbes elliptiques