RISC-V MCU中文社区

【分享】 蒙哥马利模乘介绍

发表于 全国大学生集成电路创新创业大赛 2023-05-30 23:36:57
0
1199
0

一、队伍介绍
报名编号:CICC2623
团队名称:吾开天工
二、Montgomery模乘介绍
Montgomery 模乘算法是最有效的大整数模乘算法之一它的一个显著特点是消除了mod n 的除法运算。Montgomery 算法的基本思想是计算图片alt ,设n为k比特的整数,即 图片alt; 图片alt,通常取 图片alt图片alt是r模n的逆,即 图片alt图片alt
计算 图片alt的算法:
图片alt
因为图片alt 所以 图片alt, 图片alt都可以通过简单的移位操作实现,从而消去了最复杂的除法运算。由于Montgomery 算法计算的是图片alt 的值,因此还需要进行相应的预计算和后处理来消除 图片alt的影响所以Montgomery 算法并不适合于单次的模乘运算。

喜欢0
用户评论
海绵宝宝

海绵宝宝 实名认证

学好习,写好代码

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