带有错误的环学习（Ring-LWE）是各种基于格的密码系统的基础。 基于Ring-LWE的密码系统最关键且计算量大的操作是环上的多项式乘法。 在本文中，我们介绍了几种优化技术，以利用数论变换（NTT）构建有效的多项式乘法器。 我们提出了一种优化NTT和反向NTT的位反向操作的技术。 通过其他优化，我们的多项式乘法器将所需的时钟周期从（8n + 1.5n lg n）减少到（2n + 1.5n lg n）。 通过利用常数因子之间的关系，我们的多项式乘法器能够将常数因子的数量从4n减少到2.5n，从而节省了大约37.5％的ROM存储。 此外，我们提出了一种新颖的内存访问方案，以实现蝶形运算符的最大利用。 借助这些技术，我们的多项式乘法器能够在Spartan-6 FPGA上针对维度256/512每秒执行57304/26913多项式乘法。
2022-05-12 22:02:24
901KB
1
迭代算法的具体实现过程
初始化
预处理
通过增加高次零项使将多项式的次数增加到2的幂次。
Function transform_better (a:atype):y:ytype;
y:=a;
迭代过程
For k:=1 to lg n do
对数组进行恰当的合并并将结果放到数组恰当的位置。
2021-11-14 23:28:01
445KB
1
题目：n元多项式乘法
功能： 完成两个n元多项式作乘法，给出明确的等式形式。
分步实施：
1． 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；
2． 完成最低要求：建立一个文件，实现两个一元二次多项式作乘法。
3． 进一步要求：实现三元二次多项式的乘法。有兴趣的同学可以自己扩充系统功能。
要求：1）界面友好，函数功能要划分好
2）总体设计应画一流程图
3）程序要加必要的注释
4）要提供程序测试方案
5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。
2021-08-30 10:34:37
2KB
1
实验内容及要求：
从字符文件输入两个多项式的非零系数及对应的指数，建立多项式的链式存储结构，计算这两个多项式的乘积，输出乘积多项式的全部非零系数及对应的指数到另一字符文件中。
要求输入输出字符文件中的数据格式自拟；编程语言采用C/C++。
实验目的：掌握单向链表的基本操作以及基于链表的多项式加法与乘法。
2021-05-03 09:03:01
46KB