一 蒙哥马利算法模乘介绍
蒙哥马利模乘算法主要为了进行大数运算a*b mod n,在介绍蒙哥马利模乘之前,先让我们来了解蒙哥马利约减。
1.1 蒙哥马利约减
a mod n
如果a是一个2048位的整数,n是一个1024位的整数,如果直接采用相除的方式,不论在空间还是时间上都会产生非常大的开销,是非常不划算的,因此我们通过添加一些手段来加速我们的运算。
a+sn mod n 等价 a mod n
这条等式显然是成立的。如果我们控制s的值,让a+s*n 在低1024位上全部为0,就能很好的计算a mod n。
同理a我们也可以将其拆分为a1和a0,高的1024位为a1,低的1024位为a0,那么
文章来源:https://www.toymoban.com/news/detail-743616.html
因此文章来源地址https://www.toymoban.com/news/detail-743616.html
到了这里,关于蒙哥马利算法模乘(四)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!