基于有限域的FFT算法研究及在全同态加密算法中的应用
发布时间：2021-05-19 10:02
快速傅里叶变换（Fast Fourier Transform,FFT）结合高速硬件能够实现对信号的实时处理,在图像处理、生物医疗、大数据以及云计算安全等智能领域广泛使用。但随着当前人工智能（AI）的快速发展,底层硬件面临计算能力不足的瓶颈,对底层核心算法提出更高需求。尽管数字信号处理领域中FFT算法的提出已大大提升了计算性能,但面对工程上大点数FFT变换的巨大计算量和移动终端的硬件资源限制,传统FFT算法的运算性能也无法满足高速硬件的实时性需求,对其优化加速及减少资源损耗十分必要。本文围绕FFT算法优化、硬件实现以及在全同态加密中的应用进行了研究,主要工作及创新如下:1、针对实数域和复数域上实现FFT算法不能达到高速率和低资源使用率的问题,介绍并改进了一种基于有限域的FFT算法,首先利用有限域的循环特性构造最小多项式的方式来化解FFT算法的乘加法运算次数,以满足底层算法加速的初步需求,随后对算法进行了相对应的硬件实现和优化,设计出基于GF（24）的15点FFT硬件实现框架,并对其在FPGA上完成验证。对比有限域离散傅里叶变换（Discrete Fourier Transform,DFT...
【文章来源】：杭州电子科技大学浙江省
【文章页数】：75 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第一章 绪论
1.1 课题研究背景及意义
1.2 国内外研究现状
1.2.1 FFT算法研究现状
1.2.2 FFT算法硬件实现研究现状
1.2.3 全同态加密研究现状
1.3 课题研究内容与章节安排
第二章 基础理论介绍
2.1 有限域和有限域运算概述
2.1.1 群和域
2.1.2 有限域基础
2.1.3 二进制域运算
2.2 FFT算法基础原理
2.2.1 傅里叶变换(FT)
2.2.2 离散傅里叶变换(DFT)
2.2.3 快速傅里叶变换(FFT)
2.2.4 传统快速傅里叶变换算法
2.3 算法硬件实现方式介绍
2.3.1 FPGA技术简介
2.3.2 FPGA开发流程
2.3.3 系统开发环境
2.4 本章小结
第三章 基于有限域的FFT算法研究
3.1 有限域FFT算法简述
3.2 有限域FFT算法原理
3.3 基于GF(2~4)的FFT算法实现
3.4 算法硬件实现设计
3.4.1 FPGA硬件实现
3.4.2 算法仿真验证与分析
3.5 本章小结
第四章 大整数乘法算法研究
4.1 大整数乘法概述
4.2 传统大整数乘法算法
4.2.1 Comba算法
4.2.2 Karatsuba算法
4.3 基于有限域FFT算法的大整数乘法算法设计
4.3.1 基于有限域FFT的 Schonhage-Strassen算法研究
4.3.2 算法演算
4.3.3 算法硬件实现及仿真分析
4.4 本章小结
第五章 面向全同态加密的大整数乘法算法研究
5.1 算法原理和研究
5.1.1 两种全同态加密方案对比
5.1.2 大整数乘法框架设计
5.1.3 16点FFT算法设计及其优化
5.2 算法硬件实现
5.2.1 优化前的算法架构设计
5.2.2 优化后的算法架构设计
5.3 算法性能分析与仿真
5.4 本章小结
第六章 总结与展望
致谢
参考文献
附录
【参考文献】：
期刊论文
[1]使用SMP的超大点数FFT算法研究与实现[J]. 钱炳锋,孙以泽. 电子科技大学学报. 2019(01)
[2]大整数乘法Sch?nhage-Strassen算法的多核并行化研究[J]. 赵玉文,刘芳芳,蒋丽娟,杨超. 软件学报. 2018(12)
[3]GF（28）上高矩阵为密钥矩阵的Hill加密衍生算法[J]. 刘海峰,卢开毅,梁星亮. 西南大学学报(自然科学版). 2018(11)
[4]RV32IM处理器乘法电路的设计与实现[J]. 张凯,李涛,秦晨蕊,圣飞. 微电子学与计算机. 2018(09)
[5]面向全同态加密的有限域FFT算法FPGA设计[J]. 施佺,韩赛飞,黄新明,孙玲,谢星,唐天泽. 电子与信息学报. 2018(01)
[6]变维度FFT硬件加速器结构设计及FPGA实现[J]. 张多利,张玲佳,宋宇鲲. 微电子学与计算机. 2017(12)
[7]同态加密技术及其在云计算隐私保护中的应用[J]. 李宗育,桂小林,顾迎捷,李雪松,戴慧珺,张学军. 软件学报. 2018(07)
[8]任意点存储器结构FFT处理器地址策略[J]. 夏凯锋,周小平,吴斌. 北京理工大学学报. 2017(09)
[9]有限域上置换多项式的几种构造[J]. 查正邦,胡磊. 密码学报. 2017(03)
[10]FFT算法硬件模块的高层次综合实现与优化[J]. 孟祥刚,陈瑶,高腾,梁科,李国峰. 微电子学. 2017(02)
硕士论文
[1]有限域上椭圆曲线基本算法快速实现的研究[D]. 段绍霞.青岛大学 2016
[2]一种基于Verilog的大整数除法器的实现[D]. 庞勇.西安电子科技大学 2016
本文编号：3195584
【文章来源】：杭州电子科技大学浙江省
【文章页数】：75 页
【学位级别】：硕士
【文章目录】：
摘要
ABSTRACT
第一章 绪论
1.1 课题研究背景及意义
1.2 国内外研究现状
1.2.1 FFT算法研究现状
1.2.2 FFT算法硬件实现研究现状
1.2.3 全同态加密研究现状
1.3 课题研究内容与章节安排
第二章 基础理论介绍
2.1 有限域和有限域运算概述
2.1.1 群和域
2.1.2 有限域基础
2.1.3 二进制域运算
2.2 FFT算法基础原理
2.2.1 傅里叶变换(FT)
2.2.2 离散傅里叶变换(DFT)
2.2.3 快速傅里叶变换(FFT)
2.2.4 传统快速傅里叶变换算法
2.3 算法硬件实现方式介绍
2.3.1 FPGA技术简介
2.3.2 FPGA开发流程
2.3.3 系统开发环境
2.4 本章小结
第三章 基于有限域的FFT算法研究
3.1 有限域FFT算法简述
3.2 有限域FFT算法原理
3.3 基于GF(2~4)的FFT算法实现
3.4 算法硬件实现设计
3.4.1 FPGA硬件实现
3.4.2 算法仿真验证与分析
3.5 本章小结
第四章 大整数乘法算法研究
4.1 大整数乘法概述
4.2 传统大整数乘法算法
4.2.1 Comba算法
4.2.2 Karatsuba算法
4.3 基于有限域FFT算法的大整数乘法算法设计
4.3.1 基于有限域FFT的 Schonhage-Strassen算法研究
4.3.2 算法演算
4.3.3 算法硬件实现及仿真分析
4.4 本章小结
第五章 面向全同态加密的大整数乘法算法研究
5.1 算法原理和研究
5.1.1 两种全同态加密方案对比
5.1.2 大整数乘法框架设计
5.1.3 16点FFT算法设计及其优化
5.2 算法硬件实现
5.2.1 优化前的算法架构设计
5.2.2 优化后的算法架构设计
5.3 算法性能分析与仿真
5.4 本章小结
第六章 总结与展望
致谢
参考文献
附录
【参考文献】：
期刊论文
[1]使用SMP的超大点数FFT算法研究与实现[J]. 钱炳锋,孙以泽. 电子科技大学学报. 2019(01)
[2]大整数乘法Sch?nhage-Strassen算法的多核并行化研究[J]. 赵玉文,刘芳芳,蒋丽娟,杨超. 软件学报. 2018(12)
[3]GF（28）上高矩阵为密钥矩阵的Hill加密衍生算法[J]. 刘海峰,卢开毅,梁星亮. 西南大学学报(自然科学版). 2018(11)
[4]RV32IM处理器乘法电路的设计与实现[J]. 张凯,李涛,秦晨蕊,圣飞. 微电子学与计算机. 2018(09)
[5]面向全同态加密的有限域FFT算法FPGA设计[J]. 施佺,韩赛飞,黄新明,孙玲,谢星,唐天泽. 电子与信息学报. 2018(01)
[6]变维度FFT硬件加速器结构设计及FPGA实现[J]. 张多利,张玲佳,宋宇鲲. 微电子学与计算机. 2017(12)
[7]同态加密技术及其在云计算隐私保护中的应用[J]. 李宗育,桂小林,顾迎捷,李雪松,戴慧珺,张学军. 软件学报. 2018(07)
[8]任意点存储器结构FFT处理器地址策略[J]. 夏凯锋,周小平,吴斌. 北京理工大学学报. 2017(09)
[9]有限域上置换多项式的几种构造[J]. 查正邦,胡磊. 密码学报. 2017(03)
[10]FFT算法硬件模块的高层次综合实现与优化[J]. 孟祥刚,陈瑶,高腾,梁科,李国峰. 微电子学. 2017(02)
硕士论文
[1]有限域上椭圆曲线基本算法快速实现的研究[D]. 段绍霞.青岛大学 2016
[2]一种基于Verilog的大整数除法器的实现[D]. 庞勇.西安电子科技大学 2016
本文编号：3195584
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3195584.html
