SWIFFT算法效率分析

摘要：

以SWIFFT算法为重要组成部分的SWIFFTX杂凑算法因实现效率问题未能进入SHA-3第二轮竞选.为此,研究提高SWIFFTX杂凑算法效率的方法,分析SWIFFT算法的实现过程.通过绘制快速傅里叶变换(FFT)流向图,估算实现SWIFFT算法的加/减、乘法运算量.此外,还提出一种计算中间参数ω的方法.分析结果表明:当存储空间较少时,选用16点FFT实现SWIFFT算法效率更高;当存储空间充足时,选用8点FFT实现SWIFFT算法效率更高.

关键词：杂凑函数、SWIFFT压缩函数、R-SIS问题、快速傅里叶变换、效率分析

所属期刊栏目：45

分类号：TP309(计算技术、计算机技术)

资助基金：国家重点研发计划项目2016YFB0800304

在线出版日期：2019-07-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：109-114