上区块链零知识证明：STARKs，Part-3：攻坚( 二 ) _运算

-使用蒙哥马利批量求逆来计算模逆，其输入为紫色，输出为绿色，乘法门为黑色，红色方块是唯一的模逆。-
下述代码实现了这个算法，并附有一些略微丑陋的特殊情况逻辑。如果我们正在求逆的集合中包含零，那么它会将这些零的逆设置为 0 并继续前进。
def multi_inv(self, values):partials = [1]for i in range(len(values)):partials.append(self.mul(partials[-1], values[i] or 1))inv = self.inv(partials[-1])outputs = [0] * len(values)for i in range(len(values), 0, -1):outputs[i-1] = self.mul(partials[i-1], inv) if values[i-1] else 0inv = self.mul(inv, values[i-1] or 1)return outputs
当我们开始处理多项式的求值集合划分时，这种批量求逆算法将会非常重要。
现在我们继续进行多项式运算。我们将多项式视为一个数组，其中元素 i 是第 i 次项（例如，x^3 + 2x + 1 变为 [1,2,0,1]）。以下是对某一点上的多项式求值的运算：
# Evaluate a polynomial at a pointdef eval_poly_at(self, p, x):y = 0power_of_x = 1for i, p_coeff in enumerate(p):y += power_of_x * p_coeffpower_of_x = (power_of_x * x) % self.modulusreturn y % self.modulus
思考题：
如果模数为31，那么f.([4, 5, 6], 2) 的输出是多少？
答案是：
6 * 2^2 + 5 * 2 + 4 = 38，38 mod 31 = 7 。
还有对多项式进行加、减、乘、除的代码；教科书上一般冗长地称之为加法/减法/乘法/除法。有一个很重要的内容是拉格朗日插值，它将一组 x 和 y 坐标作为输入，并返回通过所有这些点的最小多项式（你可以将其视为多项式求值的逆）：
# 构建一个在所有指定 x 坐标处返回 0 的多项式def zpoly(self, xs):root = [1]for x in xs:root.insert(0, 0)for j in range(len(root)-1):root[j] -= root[j+1] * xreturn [x % self.modulus for x in root]def lagrange_interp(self, xs, ys):# 生成主分子多项式，例如(x – x1) * (x – x2) * … * (x – xn)root = self.zpoly(xs)# 生成每个值对应的分子多项式，例如，当 x = x2 时，,# 通过用主分子多项式除以对应的 x 坐标# 得到 (x – x1) * (x – x3) * … * (x – xn)nums = [self.div_polys(root, [-x, 1]) for x in xs]# 通过求出在每个 x 处的分子多项式来生成分母denoms = [self.eval_poly_at(nums[i], xs[i]) for i in range(len(xs))]invdenoms = self.multi_inv(denoms)# 生成输出多项式，即每个值对应的分子的总和# 多项式重新调整为具有正确的 y 值b = [0 for y in ys]for i in range(len(xs)):yslice = self.mul(ys[i], invdenoms[i])for j in range(len(ys)):if nums[i][j] and ys[i]:b[j] += nums[i][j] * yslicereturn [x % self.modulus for x in b]
相关数学说明请参阅这篇文章关于“M-of-N”的部分。需要注意的是，我们还有特殊情况方法和来加速次数小于 2 的拉格朗日插值和次数小于 4 的多项式运算。
快速傅立叶变换
如果你仔细阅读上述算法，你可能会注意到拉格朗日插值和多点求值（即求在N个点处次数小于N的多项式的值）都需要执行耗费二次时间。举个例子，一千个点的拉格朗日插值需要数百万步才能执行，一百万个点的拉格朗日插值则需要几万亿步。这种超低效率的状况是不可接受的。因此，我们将使用更有效的算法，即快速傅立叶变换。
FFT 仅需要O(n * log(n))时间（即 1000 个点需要约 10000 步，100 万个点需要约 2000 万步），但它的范围更受限制：其 x 坐标必须是满足N = 2^k阶的单位根的完整集合。也就是说，如果有 N 个点，则 x 坐标必须是某个 p 的连续幂1，p，p^2，p^3 …，其中，p^N = 1 。该算法只需要一个小参数调整就可以令人惊讶地用于多点求值或插值运算。
思考题：
找出模337为1的16次单位根，且该单位根的8次幂模 337 不为1 。
答案是：

上 区块链零知识证明：STARKs，Part-3：攻坚( 二 )

上区块链零知识证明：STARKs，Part-3：攻坚( 二 )