title | tags | ||||||
---|---|---|---|---|---|---|---|
37. Miller 算法 |
|
这一讲,我们介绍 Miller 算法,它可以高效计算椭圆曲线上的配对。
首先我们回顾下 Weil 配对,它将椭圆曲线
它的具体形式:
其中,函数
Miller 算法就求解函数
- 初始
$T = P$ 和$f = 1$ - 从
$i = t - 1$ 循环至 0$f = f^2 \cdot h_{T,T}$ $T = 2T$ - 如果
$\varepsilon_i = 1$ $f = f \cdot h_{T,P}$ $T = T + P$
- 结束循环
- 返回
$f$ 的值
最后返回的函数
当
首先,我们定义一个和椭圆曲线交与
定义在椭圆曲线上的有理函数
另外,有理函数
我们可以构造上面两个有理函数的商
特别的,当直线斜率
接下来,我们将
其中
通过简单的(并不)归纳法,我们就能证明 Miller 算法输出的
下面我们举个稍微复杂的 Weil 配对的例子,过程使用 Sage 计算,内置了 Miller 算法。Sage(也称为SageMath)是一个开源的数学软件系统,旨在提供一个强大、全面的环境,用于解决各种数学问题和进行数学研究。它的语法与python类似,你可以使用 SageMathCell 在浏览器中运行 Sage 程序。
设定义在
它满足
代码如下:
p = 631
a = 30
b = 34
E = EllipticCurve(GF(p), [a, b])
print(E)
print("椭圆曲线中的元素个数: ", E.cardinality())
# 获取5-挠群的点
INF = E[0]
L_E_5 = INF.division_points(5) # [11]P == INF
E_5 = Set(L_E_5) # $5$-torsion
print("5-torsion points: ", E_5)
print("5-挠群中的元素个数: ", E_5.cardinality())
P = E([36,60])
Q = E([121,387])
weil_P_Q = P.weil_pairing(Q, 5)
print("5-挠群中点", P, "和", Q, "的Weil配对为", weil_P_Q)
# 输出
# Elliptic Curve defined by y^2 = x^3 + 30*x + 34 over Finite Field of size 631
# 椭圆曲线中的元素个数: 650
# 5-torsion points: {(121 : 244 : 1), (121 : 387 : 1), (420 : 48 : 1), (0 : 1 : 0), (531 : 613 : 1), (36 : 60 : 1), (586 : 584 : 1), (428 : 25 : 1), (586 : 47 : 1), (339 : 132 : 1), (289 : 362 : 1), (575 : 7 : 1), (511 : 23 : 1), (511 : 608 : 1), (617 : 626 : 1), (575 : 624 : 1), (595 : 221 : 1), (617 : 5 : 1), (595 : 410 : 1), (36 : 571 : 1), (531 : 18 : 1), (339 : 499 : 1), (289 : 269 : 1), (428 : 606 : 1), (420 : 583 : 1)}
# 5-挠群中的元素个数: 25
# 5-挠群中点 (36 : 60 : 1) 和 (121 : 387 : 1) 的Weil配对为 242
接下来,我们计算
因为 Weil 配对满足双线性,那么应该有
因此,使用 Weil 配对,我们可以用
代码如下:
R = 3 * P
S = 4 * Q
weil_R_S = R.weil_pairing(S, 5)
print("5-挠群中点", R, "和", S, "的Weil配对为", weil_R_S)
print("因为 R= 3P, S = 4Q,因此 weil_P_Q ^ 12 = ", weil_P_Q^12 , "和 weil_R_S 相等")
# 5-挠群中点 (617 : 5 : 1) 和 (121 : 244 : 1) 的Weil配对为 512
# 因为 R= 3P, S = 4Q,因此 weil_P_Q ^ 12 = 512 和 weil_R_S 相等
这一讲,我们介绍了可以高效计算配对的 Miller 算法,并使用 Sage 写了一个 Weil 配对的例子。