wuvin
Always take risks!
Toggle navigation
wuvin
主页
实验室的搬砖生活
机器学习
公开的学术内容
公开的其他内容
About Me
归档
标签
友情链接
ZYQN
ihopenot
enigma_aw
hzwer
杨宗翰
关于NTT的一些研究
? FFT ?
2017-03-19 20:06:26
417
0
0
wuvin
? FFT ?
首先回顾了FFT的性质与原理，发现如果单位根w满足一下条件就可以达到FFT的效果。$w^n=1,w^{\frac{n}{2}}=-1$。 所以根据如上理论，NTT的要求w必须是模意义下的原根，这样才可以满足以上要求。而模数mod必须满足$mod=1,2,4,p,2p,p^n$ （p是奇质数）。 ###原根的判定 在模mod的意义下$x^{\phi(mod)}\equiv 1$，并且不存在比$\phi(mod)$更小的次方满足等于1的条件。
上一篇:
BC 2nd Anniversary总结
下一篇:
7.5集训总结
0
赞
417 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
wuvin
没有帐号? 立即注册