零知识证明 - 理解FFT的蝶形运算

2020-07-20 10:10 栏目:经验之谈 来源:网络整理 查看()

这个周末我有空谈谈我对快速傅立叶变换的理解。学习零知识证明的小伙伴理解这一部分很方便。从一开始,零知识就证明Groth16算法是基于QAP问题的:

零知识证明 - 理解FFT的蝶形运算

在使用Groth16计算证明之前,需要计算h。目前,快速傅立叶变换算法被广泛使用。

1.快速傅立叶变换计算原理

为了学习快速傅立叶变换的计算原理,我们仍然需要看第三十章(多项式和快速傅立叶变换)的算法介绍。算法介绍,讲述事物,讲述前因后果清晰,逻辑性强,细致入微。本章从多项式的表示开始,多项式可以用两种方式表示:系数表示和点值表示。

系数表示对多项式加法很友好,时间复杂度为O(n),但多项式乘法不友好,时间复杂度为O(n * 2)乘以多项式的一项。点值表示对多项式乘法友好,时间复杂度为0(n),但多项式加法不友好。

离散傅立叶变换使用特殊的点来计算该值。这些特殊点是单位根的幂。利用这些特殊的点,系数表示和点值表示之间的关系可以通过快速傅立叶变换来计算。时间复杂度为0。

算法简介该图可以很好地解释这些计算之间的关系:

零知识证明 - 理解FFT的蝶形运算

在系数表示的情况下,多项式乘法的计算复杂度为0(n * 2)。如果首先将其转换为点值表示,然后转换为系数表示,则计算复杂度为0(NLO gn)。

n次的单位根

n次有n个单位根。单位根满足w**n=1。

零知识证明 - 理解FFT的蝶形运算

这些单位根有一些性质或定理:

零知识证明 - 理解FFT的蝶形运算

快速傅立叶变换的基本原理

快速傅立叶变换用于计算离散傅立叶变换,时间复杂度为0。原理是将多项式分解成奇数和偶数部分(假设n是2的幂,n不是2的幂,后面有相应的算法):

零知识证明 - 理解FFT的蝶形运算

也就是说,计算A(x)的对应值可以分解成两个子多项式(奇偶性),并且每个多项式的点是前一个多项式的平方。从递归的角度来看,我们可以看到这些子多项式可以进一步划分为更小的多项式。整个计算的复杂性:

零知识证明 - 理解FFT的蝶形运算

如果输入点也分为两部分,每部分为n/2,k的范围为0~n/2,则为:

这就是传说中的“蝴蝶计算”。在两个子多项式的值的计算完成之后,原始多项式的两个相差n/2的点的值是一加一减去两个子多项式的值。

整个计算算法的伪代码如下:

零知识证明 - 理解FFT的蝶形运算

W _ n k,作用于第二子多项式的结果,称为旋转因子。整个蝶式操作可以用直观的图形表示如下:

零知识证明 - 理解FFT的蝶形运算

八阶多项式示例

算法介绍清楚地给出了8阶多项式快速傅立叶变换的计算过程:

零知识证明 - 理解FFT的蝶形运算

在阶段s=1的情况下,也就是说,在底层的两个一阶多项式被合并。旋转因子为w _ 2 0。注意,该层的输出结果将被用作下一级s=2的输入,并且该层的旋转因子是w _ 4 {0,1}。这一层处理“两个”二阶多项式的组合。在奇偶除法的情况下,第一/第二元素和第三/第四元素(跨度2)进行蝶形运算。依此类推,直到阶段s=3结束。

整个过程可以用Merkle树图像来表示:

零知识证明 - 理解FFT的蝶形运算

注意最低元素的位置。递归除法不再是连续的。算法介绍还总结了相应的计算方法,感兴趣的合作伙伴可以查看。

你可以回到大脑,体验这个公式:

零知识证明 - 理解FFT的蝶形运算

由于特殊的取点原因(w 2等于阶数减半),次多项式的值也是结果多项式的一半。因为点被分成一半(只是次多项式的阶),并且因为旋转因子只是正和负,所以存在蝴蝶关系。每一层的子多项式的元素被加倍。

2.快速傅立叶变换通用计算扩展

在理解了两点快速傅立叶变换的计算逻辑后,它可以扩展到一般的计算。推荐另一个网站(注意多项式符号与上面的略有不同):

http://www.bealto.com/gpu-fft2_fft.html

零知识证明 - 理解FFT的蝶形运算

多项式不再分成“奇数”和“偶数”部分,而是分成p个部分,每个部分都有q个元素:

零知识证明 - 理解FFT的蝶形运算

X_u是系数。u的范围是0-P-1。首先,在此划分下定义离散傅立叶变换计算:

零知识证明 - 理解FFT的蝶形运算

DFT_Q代表Q个元素,x[u]代表Q个元素序列,每个元素序列跨越p,p * q=n。

如果输入也被分成p个部分(就像在等分的情况下把输入分成两个部分),k可以表示为k=v Qj,v=0.q-1,j=0.p-1。其中DFT_Q (x[u])表示为z[u]。

零知识证明 - 理解FFT的蝶形运算

也就是说,当P*Q被分组时,蝶形运算如下:

零知识证明 - 理解FFT的蝶形运算

此外,y的每个元素的计算可视为一个新的离散傅立叶变换:

零知识证明 - 理解FFT的蝶形运算

在了解这些的前提下,可以清楚的看到网站给出的P*Q分组计算示意图:

零知识证明 - 理解FFT的蝶形运算

整个快速傅立叶变换计算包括三个部分:

1/P DFT_Q计算(z[0],z[1],z[P-1]) 2/乘以旋转3/量子密度泛函理论计算

在q DFT_P计算之后,有必要将P计算数据“分散”到以q为偏移的特定位置。

摘要:

零知识证明,在格罗16的计算中,快速傅立叶变换计算是用来计算h的。快速傅立叶变换的蝶形运算是理解快速傅立叶变换计算的基础。二分法情况下的计算相对清晰,详细的推导过程在算法介绍中给出。P*Q的一般计算和推导比较复杂。

微信二维码
售前客服二维码

文章均源于网络收集编辑侵删

提示:币友交流QQ/WX群请联系客服加入!

郑重申明:资讯文章为网络收集整理,官方公告以外的资讯内容与本站无关!
虚拟币开发,虚拟币交易平台开发,山寨币交易平台开发 Keywords: 虚拟币开发 虚拟币交易平台开发 山寨币交易平台开发