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

59，146，30，297，278，191，307，40
【上区块链零知识证明：STARKs，Part-3：攻坚】你可以通过进行诸如[print(x) for x in range(337) if pow(x, 16, 337) == 1 and pow(x, 8, 337) != 1]的操作来得到上述答案列表。当然，也有适用于更大模数的更智能的方法：首先，通过查找满足pow(x, 336 // 2, 337) != 1（这些答案很容易找到，其中一个答案是 5）的值 x 来识别单个模 337 为 1 的原始根（不是完美的正方形），然后取它的 (336 / 16) 次幂。
以下是算法实现（该实现略微简化，更优化内容请参阅此处的代码）：
def fft(vals, modulus, root_of_unity):if len(vals) == 1:return valsL = fft(vals[::2], modulus, pow(root_of_unity, 2, modulus))R = fft(vals[1::2], modulus, pow(root_of_unity, 2, modulus))o = [0 for i in vals]for i, (x, y) in enumerate(zip(L, R)):y_times_root = y*pow(root_of_unity, i, modulus)o[i] = (x+y_times_root) % moduluso[i+len(L)] = (x-y_times_root) % modulusreturn odef inv_fft(vals, modulus, root_of_unity):f = PrimeField(modulus)# Inverse FFTinvlen = f.inv(len(vals))return [(x*invlen) % modulus for x infft(vals, modulus, f.inv(root_of_unity))]
你可以尝试键入几个输入，并检查它是否会在你使用时，给出你期望得到的答案。例如：
>>> fft.fft([3,1,4,1,5,9,2,6], 337, 85, inv=True)[46, 169, 29, 149, 126, 262, 140, 93]>>> f = poly_utils.PrimeField(337)>>> [f.eval_poly_at([46, 169, 29, 149, 126, 262, 140, 93], f.exp(85, i)) for i in range(8)][3, 1, 4, 1, 5, 9, 2, 6]
傅立叶变换将[x[0] …. x[n-1]]作为输入，其目标是输出x[0] + x[1] + … + x[n-1]作为第一个元素，x[0] + x[1] * 2 + … + x[n-1] * w**(n-1)作为第二个元素等等。快速傅里叶变换通过将数据分成两半，并在这两半数据上进行FFT，然后将结果粘合在一起的方式来实现。
这是信息在 FFT 计算中的路径图表。注意 FFT 如何基于数据的两半内容进行两次 FFT 复制，并进行“粘合”步骤，然后依此类推直到你得到一个元素。
一般而言，想要更直观地了解 FFT 工作原理以及 FFT 以及多项式数学，我推荐这篇文章；关于 DFT 与 FFT 的一些更具体的细节，我推荐觉得这篇文章的思路还不错。但是请注意，大多数关于傅里叶变换的文献都只谈到关于实数和复数的傅里叶变换，并没有涉及素域。如果你发现这部分内容实在太难了，并且也不想去理解它，那就把它当成某种诡异的巫术就行了——它之所以有用是因为你运行了几次代码并证明这玩意儿确实有用——这样你心里就舒服多了。
干货 |，Part-3：攻坚（下）
原文链接:

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

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