RISC-V MCU中文社区

【分享】 NTT设计介绍

发表于 全国大学生集成电路创新创业大赛 2023-05-30 21:20:00
0
1556
1

一、队伍介绍
报名编号:CICC2623
团队名称:吾开天工
二、NTT(Number Theoretical Transform)
大数乘法是公钥加密系统中最为核心的模块,同时,也是RSA、全同态等加密方案里最耗时的模块,传统的按位乘法需要将一个输入数据的每一位去乘以另一个数据的每一位,其算法时间复杂度为图片alt。NTT可以看作是定义在有限域上的快速傅里叶变换,算法时间复杂度为图片alt它基于某个质数的单位原根的幂次方根进行运算,所有的操作都在有限域内进行,避免了频繁的浮点数运算,可有效提高乘法算法的计算速度和精度。
NTT可使用Gentleman-Sande蝶形变换实现,以正常顺序输入,以位反转顺序输出。N点的NTT运算由 图片alt级组成,每一级执行图片alt 次蝶形变换。因此,一个N点的NTT共执行 图片alt次蝶形变换,以下是8点NTT的信号流图:
图片alt
对NTT进行硬件实现的步骤分以下四步:
1)索引计算 2)下载数据 3)执行蝶形计算 4)存储数据
步骤1和2中产生蝶形运算输入数据的读地址,并从存储器中读取数据;步骤3和4执行蝶形变换操作,并且使用在索引计算步骤期间生成的读取地址将输出数据写入存储器中。

喜欢1
用户评论
海绵宝宝

海绵宝宝 实名认证

学好习,写好代码

积分
问答
粉丝
关注
  • RV-STAR 开发板
  • RISC-V处理器设计系列课程
  • 培养RISC-V大学土壤 共建RISC-V教育生态
RV-STAR 开发板