作业帮蒙哥马利约减是怎么回事?
来源：学生作业帮 编辑：拍题作业网作业帮 分类：综合作业 时间：2024/04/29 07:03:56
蒙哥马利约减是怎么回事?
资料上说：
“模乘过程中复杂度最高的环节是求模运算,因为一次除法实际上包含了多次加法、减法和乘法,如果在算法中能够尽量减少除法甚至避免除法,则算法的效率会大大提高.“
“我们最终实现了不含除法的模幂算法,这就是著名的蒙哥马利算法”
速幂运算的好处是减少了运算量,极大地提高了速度.例如A^65525（A的65535次幂）,原始算法要做65535－1＝65534次乘法,而快速幂运算只需要做(16－1)×2＝30次乘法.
原理其实很好懂,假设要计算A^B,即底数是A,指数是B.把B写成二进制形式,拿4位来举例：B＝b4b3b2b1（二进制）.
先用B＝1111（二进制）来做解释.显然A^B ＝ A × A^2 × A^4 × A^8.
又显然,
A^2 ＝ A × A,
A^4 ＝ A^2 × A^2,
A^8 ＝ A^4 × A^4.
假如B的二进制位数更多,则依此类推.
上面这段看懂了吗?如果看懂的,就应该能够写出B＝1111（二进制）情况下,A^B的快速幂运算程序.
“模乘过程中复杂度最高的环节是求模运算,因为一次除法实际上包含了多次加法、减法和乘法,如果在算法中能够尽量减少除法甚至避免除法,则算法的效率会大大提高.“
“我们最终实现了不含除法的模幂算法,这就是著名的蒙哥马利算法”
速幂运算的好处是减少了运算量,极大地提高了速度.例如A^65525（A的65535次幂）,原始算法要做65535－1＝65534次乘法,而快速幂运算只需要做(16－1)×2＝30次乘法.
原理其实很好懂,假设要计算A^B,即底数是A,指数是B.把B写成二进制形式,拿4位来举例：B＝b4b3b2b1（二进制）.
先用B＝1111（二进制）来做解释.显然A^B ＝ A × A^2 × A^4 × A^8.
又显然,
A^2 ＝ A × A,
A^4 ＝ A^2 × A^2,
A^8 ＝ A^4 × A^4.
假如B的二进制位数更多,则依此类推.
上面这段看懂了吗?如果看懂的,就应该能够写出B＝1111（二进制）情况下,A^B的快速幂运算程序.