求蒙哥马利算法的通俗解释或易懂伪码

难道是模幂运算？那玩意儿看了n久还是不太懂。

是的，太难懂了 【 在 bebop 的大作中提到: 】 : 难道是模幂运算？那玩意儿看了n久还是不太懂。

快速幂运算的好处是减少了运算量，极大地提高了速度。例如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的快速幂运算程序。

然后再来看B＝b4b3b2b1（二进制）的情况。这时候A^B ＝ A1 × A2 × A3 × A4。 其中， A1 ＝ A（如果b1＝1）或者1（如果b1＝0）， A2 ＝ A^2（如果b2＝1）或者1（如果b2＝0）， A3 ＝ A^4（如果b3＝1）或者1（如果b3＝0）， A4 ＝ A^8（如果b4＝1）或者1（如果b4＝0）。 假如B的二进制位数更多，则依此类推。 这一段看懂了吗？如果看懂的，我不用继续解释，能不能把上面B＝1111（二进制）的程序改一改，加入对b4、b3、b2、b1等于0或者1的条件分支判断，让它变成A^B的快速幂运算程序？ 最后补充说明：上面的解释没有提到模运算（mod X），但实际上在模运算之下也是可行的（表达得不太严谨，不管了，又不是写论文）。

这直接就用二进制来解释了，我连最基本的都没有看懂。

这个是蒙哥马利算法？ 资料上说： “模乘过程中复杂度最高的环节是求模运算，因为一次除法实际上包含了多次加法、减法和乘法，如果在算法中能够尽量减少除法甚至避免除法，则算法的效率会大大提高。“ “我们最终实现了不含除法的模幂算法，这就是著名的蒙哥马利算法” 【 在 dragon2000 的大作中提到: 】 : 然后再来看B＝b4b3b2b1（二进制）的情况。这时候A^B ＝ A1 × A2 × A3 × A4。 : 其中， : A1 ＝ A（如果b1＝1）或者1（如果b1＝0）， : ...................

不好意思，我讲的是快速幂运算算法。

之前还没见过蒙哥马利算法，1楼的信息不全被误导了。现查的资料，暂时只查到这么一句： 1985年，Peter Montgomery发现了一种只要乘法和数的位移就可以实现模乘运算的灵巧算法，这就是著名的蒙哥马利模乘算法。 再查到这个页面： http://teal.gmu.edu/courses/ECE543/project/topics/description/sp_implementation.html 摘抄英文： Project SPI-3 Title: Modular multiplication using Montgomery method. Description: Montgomery method is considered as a fastest algorithm for modular multiplication reported in the open literature. (At the ramp session of the last CRYPTO'95 Josh Benaloh announced that a faster algorithm was developed in Microsoft, but the details were not revealed, and the algorithm remains proprietary.) The idea of Montgomery algorithm is similar to multiplication using Fast Fourier Transform. We want to compute C=A*B mod N. The arguments A and B are first transformed to other domain by computing A'=A*2^n mod N, and B'=B*2^n mod N. In this new domain modular multiplication can be performed significantly faster than in the original domain. This is achieved by computing C'=A' * B' * 2^-n mod N = (A*B) * 2^n mod N = C*2^n mod N. The return to original domain is equivalent to multiplication by 1 in a new domain (C=1*C' * 2^-n mod N). Modular exponentiation is a basic transformation of majority of public key cryptoalgorithms. In exponentiation, a long sequence of modular multiplications is performed. For such sequence, input and output transformations are performed only once. Switching to other domain can therefore significantly speed-up the whole exponentiation. Knowledge of Montgomery algorithm is crucial for designers of majority of today's software and hardware public-key-cryptosystem implementations. Your task is to develop the efficient implementation of Montgomery algorithm, and compare your implementation with implementations of modular multiplication available in public domain (RSAREF, PGP, or PEM). 粗略解释一下上面这段： 如果直接计算C=A*B mod N，必须做很费时的mod N运算。从我前面讲的快速幂运算算法可知，乘法运算要进行多次，所以mod N运算也需要多次，比较慢。 假如我们做个转换，A-->A'，B-->B'，然后计算C'=A'*B' mod N，这时mod N运算可以快得多（当然这个转换是需要技巧的）。等到所有乘法运算都做完之后，最后结果再做一次转换，C'-->C，就转回到原本需要的结果了。 这个跟快速乘法运算有点类似：先用快速傅立叶变换，A-->A'，B-->B'，然后乘法变加法，C'=A'+B'，最后来个傅立叶逆变换，C'-->C，那么得到的C=A*B。加法当然比乘法快得多。

然后就是蒙哥马利算法之中，那个神奇的转换了： A'=A*2^n mod N， B'=B*2^n mod N， 显然，乘以2^n就是左移n位。至于mod N嘛……我相信n足够大，并且取某些特定值的时候，mod N可以变成不是除法的运算。例如，变成少量乘法、加减法。 由于N是奇数（通常还是大素数或者两个素数的乘积），所以2^n与N的最大公约数是1。2^n有乘法逆元（mod N域内），表示成2^-n（mod N），实际上逆元也是一个正整数，2^n乘这个整数会得1（mod N）。求逆元的算法不讨论了，欧几里得算法是最常规的一种。 显然，上述逆转换就是： C=C'*2^n-1 mod N 我是现炒现卖的，原理大致是这些。具体的实现细节肯定还有很多问题，例如n值怎样选取，我就没有查到。貌似这里就衍生出不同的技巧性算法。