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