37.Miller算法

title: 37. Miller 算法 tags: zk abstract algebra elliptic curve group theory finite field pairing WTF zk 教程第 37 讲：Miller 算法 这一讲，我们介绍 Miller 算法，它可以高效计算椭圆曲线上的配对。 Miller 算法 首先我们回顾下 Weil 配对，它将椭圆曲线 $m$-挠群上的两个点 $P, Q$ 映射到 $m$ 次单位根上： $$ em: E[m] \times E[m] \to \mum $$ 它的具体形式： $$ em(P, Q) = \frac{fP(Q+X)}{fP(X)} / \frac{fQ(P-X)}{fQ(-X)} $$ 其中，函数 $fP$ 和 $fQ$ 为定义在椭圆曲线上的有理函数，满足： $$ \text{div}(fP) = m[P] - m[O] $$ $$ \text{div}(fQ) = m[Q] - m[O] $$ 1.1 算法步骤 Miller 算法就求解函数 $fP$ 的高效算法，你可以把它理解为计算配对的 Double-And-...