本文主要是介绍蒙哥马利算法模乘（四），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一 蒙哥马利算法模乘介绍
蒙哥马利模乘算法主要为了进行大数运算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，那么
因此
这篇关于蒙哥马利算法模乘（四）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
