本文是一篇工程硕士论文，本文设计的可重构NTT架构能够支持模数的位宽为24位和4种多项式维度的重构操作。在性能方面有一定的 高，这也表明了该架构灵活性较高。
第1章绪论
1.1课题研究的目的和意义
1.1.1后量子密码应用的需求
随着信息技术的快速发展，每时每刻都有海量的信息被传输，这为社会的发展，人民的生活 供了便利。在信息传输如此密集的今天，保护信息传输的安全显得十分重要。信息安全主要是指保护信息及信息系统不被未授权地访问、使用、泄漏、干扰、修改、损毁，旨在保证信息的机密性、完整性、可用性、真实性、可追溯性。现代密码算法是信息安全实现的基础，可分为对称密码算法，和非对称密码算法。对称密码算法在对明文加密和对密文解密时用到的密钥相同，加密解密速度快。非对称密码算法又称公钥密码算法，使用一对密钥，包括公钥和私钥，公钥是公开的，而私钥是私有的。公钥密码的特点是加解密计算复杂，加解密用到的私钥和公钥虽然存在特殊的数学关系，但是无法轻易地通过公钥去计算出私钥，这就为一些需要通信安全的环境 供了解决方案。
早在1994年，传统的非对称加密体制如RSA(Rivest Shamir Adleman)[1]、椭圆曲线加密(Elliptic Curve Cryptography,ECC)[2]逐渐被Shor[3]、Grover[4]等量子算法在多项式时间内破解，这会致使加密信息的安全性大大降低。2019年1月，IBM公司在消费电子展展示了世界首款商业化量子计算机IBM Q SystemOne，该计算机具有20量子比特的计算能力[5]。同年Google公司在《Nature》上公开发布了具有53量子比特的“悬铃木”量子计算机，声称可以在200秒内解决经典计算机需要计算一万年的问题[6]。2020年中国科学技术大学实现了具有76个光子的量子计算原型机“九章”，该量子计算机只需200秒就可以解出高斯玻色取样这一问题[7]。在量子计算时代到来之前，人们需要尽快 出应对量子计算的方案。
..............................
1.2国内外研究现状
当前面向格密码算法的研究主要体现在两个不同的层次：核心计算模块—NTT和NTT中的基本计算单元—模运算。下面分别介绍这两个层次的研究现状。
格密码中多项式乘法是最耗时的运算，NTT和INTT是大多数基于RLWE和MLWE的后量子密码算法中的核心计算模块，降低其计算复杂度是关键的优化方向之一。早在2012年，文献[30]采用NTT代替FFT在有限域下进行运算，计算基于RLWE的格密码中的多项式乘法，避免了FFT中浮点数精度与复数运算的问题，同时采用负包卷积（Negative Wrapped Convolution，NWC）算法加快了多项式乘法的运算速度。这与文献[31] 出的基于FFT的RLWE加密方案相比，资源消耗显著降低，解决了多项式乘法运算资源消耗过大的问题，使得RLWE加密方案具备了实用性。文献[23][24]也使用NWC算法避免了向量补零填充带来的NTT运算规模翻倍问题，进而降低多项式乘法的复杂度和存储开销。NWC算法在处理NTT和INTT的过程中，加入预处理和后处理操作，替代了原本的NTT和INTT。NTT有变体离散加权变换，INTT有变体逆离散加权变换。而离散加权变换相比NTT引入了多余的预处理，逆离散加权变换相比INTT引入了后处理，增加了计算量。文献[32]通过调整NTT算法中蝶形单元的调用顺序，减少了实时生成旋转因子的模乘次数，并且还通过更改NTT算法中旋转因子初值的方法消除了预处理，进一步降低了NTT的计算复杂度。随即这种NTT优化方法用在了之后的研究中[33][34][35]，但是这种优化方法不能应用于INTT。文献[34]虽然通过预先计算合并后处理和1n缩放和的方式，优化了后处理的模乘数量，但是预计算旋转因子的存储资源从�增加到3�/2。文献[36]虽然消除了INTT后处理的计算周期，但是这种方法没有减少模乘的数量，并且大幅增加了硬件开销。文献[37]在8位处理器上的软件实现中，通过避免后处理中的n1操作，减少了INTT的计算量。与文献[34]的方法相比，已经没有了预计算旋转因子的存储开销，也没有实际消除后处理中1n缩放操作。上述方案的不足之处在于其一算法本身没有时间上的优化，其二不能同时用于正变换和逆变换中。
................................
第2章格与多项式相关理论概述
2.2快速傅里叶变换
离散傅里叶变换的出现使得离散信号可以在频域上进行计算，但是在实际计算中，DFT存在大量的复数加法和乘法，极大的限制了计算机的计算性能。为了 高DFT的计算效率，在1965年，库利（Cooley）和图基（Tukey） 出了一种快速计算DFT的方法，即快速傅里叶变换（Fast Fourier Transform,FFT）。
FFT有基2、基4、混合基等算法，而CT 出的基于时域抽取的基2-FFT算法是目前应用较多的DFT快速计算方法，它的优势在于方便硬件电路的实现和算法思想相对简单，局限在于其计算点数必须是2的次幂。在计算点数相同情况下，DFT的计算复杂度为2O(n)，基2-FFT的计算复杂度为O(nlogn)。如表2-1所示，随着计算点数n的增加，基2-FFT和DFT的计算量的比值也会增加。
工程硕士论文怎么写
CT基2-FFT的算法思想是根据旋转因子的特殊性质，把n点长序列的计算转换成两个n/2点分别进行计算，然后再将n/2点转换到两个n/4点进行计算，以此类推，最后将4点的DFT转换成两个2点的DFT进行计算。
.............................
2.3NTT快速算法分析
NTT是离散傅里叶变换在有限域的变体，目前存在着时域抽取（Decimation-In-Time,DIT）和频域抽取（Decimation-In-Frequency,DIF）两种算法。DIT对应Cooley-Tukey快速傅里叶变换（CT-FFT）算法，DIF对应Gentlemen-Sande快速傅里叶变换（GS-FFT）算法。NWC算法使用的NTT不需要补零倍增，但是NTT的输入向量需要做预处理操作，输出向量需要做后处理操作。为了避免预处理操作和减少后处理，本文需要对NTT和INTT的快速算法进一步分析。
朴素的基2时域抽取快速数论变换与快速傅里叶变换推导过程一致，所以这里不对其进行推导。前文介绍的NWC并没有消除预处理操作，而文献[50] 出的低复杂度数论变换解决了这个问题，为了不引起歧义，这里采用低复杂度的基2时域抽取快速数论变换（Low-complexity Radix-2 Decimation-In-Time Fast NumberTheoretic Transform,LDIT-FNTT）这种叫法，下文不再赘述。
...........................
第3章可重构数论变换算法研究...........................20
3.1 NTT快速算法分析.............................20
3.1.1基2时域抽取快速数论变换算法分析..........................20
3.1.2基2频域抽取快速数论变换算法分析......................23
第4章可重构架构实现与NTT快速算法映射验证.........................41
4.1 NTT可重构架构设计..............................41
4.1.1经典NTT架构设计.........................41
4.1.2可重构NTT架构设计...................................42
结论.......................56
第4章可重构架构实现与NTT快速算法映射验证
4.1 NTT可重构架构设计
本节首先分析了经典NTT架构的设计，该架构针对单一模数及点数。在此基础上，为了满足可重构计算的特性，将蝶形单元替换成了PE阵列，增加了ROM存储单元，进而设计了可重构的NTT架构。
4.1.1经典NTT架构设计
NTT单元架构有两大类模块，分为控制逻辑单元模块和运算逻辑单元模块。运算逻辑单元模块包括蝶形计算单元，蝶形单元运算由模加，模减，模乘运算模块组成。控制逻辑由控制单元组成，控制单元控制着地址发生器的地址，旋转因子的调度，蝶形运算的开始或结束，以及系数存储单元的调度。经典NTT单元架构如图4-1所示。下面是对图4-1的各模块功能的 述。
（1）旋转因子存储单元
该模块存储的是参与运算的旋转因子不同次幂的值，由控制单元直接控制，在参与蝶形运算时，通过该模块 供所需旋转因子的值，主要参与蝶形单元模块中的模乘操作。
（2）系数存储单元
该模块存储参与运算的多项式系数，通过地址发生器调度参与蝶形单元运算的多项式系数，控制单元控制系数的读写。
（3）地址发生器
该模块产生读写数据的地址信号，该地址信号控制存储系数RAM的地址，内部ROM地址。若存储系数的存储体是由多个小存储体组成，则该模块还将产生控制选择器的地址。
（4）蝶形运算单元
该模块为整体NTT架构的核心，对系数存储和旋转因子单元输入的数据进行运算，运算结果存放在系数存储单元中。
（5）控制单元
该模块产生与上述模块交互的控制信号，控制着每轮的蝶形运算需要的旋转因子，整体运算的读写时序，NTT的状态控制，以及地址发生器产生的地址。
工程硕士论文参考
....................................
结论
已公布的格密码协议中的安全参数多种多样，能够支持数论变换的格密码方案也比较多。基于格的后量子密码的安全等级和计算性能大都受到格中模数和多项式维度的限制，格密码协议中的多项式乘法是最耗时的运算，而数论变换的快速算法能加速格中多项式乘法的运算速度。针对不同的数论变换快速算法是格密码领域的研究重点。本文针对数论变换的模数和计算点数不同的问题进行了研究，设计了调和数论变换和逆数论变换算法。本文所做的主要工作如下：
（1）针对NTT算法本身，本文对基2的基于DIT快速数论变换，和基于DIF的快速数论变换进行了研究并总结了规律。通过奇偶分解的方法，将n点的数论变换，转化为了n/2点的数论变换。本文证明了关于基于频域抽取的逆数论变换，并给出了相应的数据流图。
（2）本文针对整体的多项式乘法过程推导出了调和数论变换及逆变换公式，该公式是基于应用K-RED模约简算法的蝶形单元进行推导的。通过将K-RED中的参数k，预处理因子2n及旋转因子n融合进NTT公式，改变旋转因子的初始值，就可以减少n次预处理。通过将K-RED-2x中的参数k，后处理因子2in及旋转因子in融合进INTT公式，达到了减少n次后处理的目的。
（3）通过分析比较不同的模约简算法的特点，选择了可适配NTT的不同模数，且适合可重构的NTT的模约简算法K-RED，并根据K-RED算法设计了可重构的NTT架构及PE阵列，之后设计了可重构的模加模减模乘单元，用来构成可重构的蝶形单元。
（4）完成了对原根的取法的分析，以及本文设计的HNTT和HINTT的算法验证，可重构NTT架构的逻辑综合。
参考文献（略）