Montgomery Powering Ladder算法笔记
算法出处
Koc C K, Paar C. The Montgomery Powering Ladder[C]. CHES 2002, LNCS 2523, pp. 291–302, 2003.
1. 目的
计算, 其中。
2. 思路
关于k,用到了四个记号——从左到右(高位到低位)的截断
【就是取k的最高位到第j位】
【就是取k的最高位到第j+1位,比短一个比特】
简单对比,这四个值有如下关系:
如果,则 ,
如果,则 ,
根据此公式,在计算时,可设两个寄存器R0和R1,迭代时这两个寄存器按如下规则更新。
如果,则 ,
如果,则 ,
3. 算法
根据上述想法,Montgomery Powering Ladder算法描述如下。
可并行性:R0和R1的乘法和平方可以交给两个不同的乘法器来并行。