python中乘法运算,用python加减乘除
命令
对于椭圆曲线算法，我们经常会遇到数据量很大的多项式乘除运算，比如：给定一个整数n，如何求出一个椭圆曲线方程，使其有理点群阶为n(这里是希尔伯特模多项式)；都有涉及)；或者，给定一条椭圆曲线的方程，计算该曲线在有限域上的点数(这里涉及除法多项式)。
多项式除法在一定情况下可以转化为多项式乘法。所以如何快速计算多项式乘法是一个很有意义的问题。实际上，处理这两个多项式的更好的算法是使用NTT快速数论变换。但有些地方还没想好怎么做，先梳理一下FFT算法的实现。
这篇文章偏向于python的实现。(毕竟具体教学的文章很多。
我写过一些不是那么“直接”的关于傅立叶变换的文章。作为参考，Alepha E E:关于复变量(V)从傅里叶变换到四分方的注记，以及一些几何推广。胡安兰。胡志。Comalephae E:从[向量]的角度谈谈函数(例如：傅立叶变换)zhuanlan.zhihu.com
(这两篇文章我写的比较早，有些略显幼稚。)
数据结构
我准备用Python来做。Python附带了一个字典数据类型，多项式类就是基于这个数据类型定义的。
首先我们要搞清楚我们希望多项式具有什么样的代数结构，也就是从多项式指数到多项式系数的内射性。因此，对于多项式
存储形式：字典的键值是多项式的指数，值是多项式对应的指数的系数。
在构造的时候，可以直接输入符合这样一个多项式的字典。
在构造多项式之前，至少要有加法。添加时，如
，与
以字典为准，特拉弗斯
索引并确定它是否在
如果是，则添加相应键值的值，并消除和的相应指数；
如果没有，则直接添加到返回的结果中。
傅里叶变换
对于普通乘法，如
，需要做些什么
时代周刊。
傅立叶变换用于变换原始：
译成
当然，以上两种表示可以是对等的。
注意，单位根具有这样的性质：
，以及
从而可以重复进行计算。
向上(此处
是两个不同的值，不管上述多项式系数如何)
比如对这个多项式做傅里叶变换。
首先手动组织，但是有
进一步地
这样，我们可以发现，当我们重新计算时：对于的形式
手术进行了4次；
对于表单
手术做了两次；
对于表单
的操作执行了一次。
利用单位根的“半”性质可以代换单位根。
这就是乘法中傅里叶变换的本质。
通过卷积定理，我们可以满足
这确保了产品的性能在转化前后都得到满足。
附上代码。
def FFT 4多项式(poly，max_deg):
Ind_coe=poly.ind_coe #其中Ind_coe是多项式的指数系数字典
如果yjdy(max _ deg)[3:] 1 :#这里的两个判断是为了初始化。
max _ deg=2 * * len(yjdy(max _ deg)[2:]))
M=最大度数
ind _ Coe={ I:ind _ Coe[I]if I in ind _ Coe else 0 for I in range(max _ deg)}
否则：
M=最大度数
ind _ Coe={ I:ind _ Coe[I]if I in ind _ Coe else 0 for I in range(max _ deg)}
ans={}
m=len(yjdy(max_deg)[3:])
对于范围内的项目(max_deg):
t=1
tmp_ind=ind_coe.copy()
max_deg=len(tmp_ind)
while len(tmp_ind)！=1:
unit _ root=NP . exp(2 * math . pi * Complex(0，1)*item*2**(m-t)/(M))
tmp_ind={ I:tmp _ ind[I]tmp _ ind[I max _ deg//2]* I在tmp _ ind中的unit _ root if I max _ deg//2 }
t=1
max_deg=max_deg//2
ans[item]=tmp_ind[0]
返回多项式(ans)
对于逆变换，只需要取单位根的指数的复数。
对于多项式的数据结构，可以自己实现。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。