如何高效进行模乘、模幂运算？

​ 加密算法中，模运算（包括模乘、模幂运算）是难以避免的，如何高效地进行模运算，是提高算法效率的一个关键。

​ 在数学上，模运算相当于是取余数的过程。以 x ÷ n = c ⋯ ⋯ d x \div n = c \cdots\cdots d x÷n=c⋯⋯d 为例，其中 0 ⩽ d < n 0 \leqslant d < n 0⩽d = b d >= b d>=b do d ← d − b \qquad d \leftarrow d - b d←d−bendreturn d d d . 评估

​ 在计算机以及其他的硬件设备中，比起加法、乘法运算，除法运算的效率相当慢。故，计算方法1虽然表达简洁，但是效率不高。计算方法2利用减法操作，取代了除法运算，但是当 a a a 和 b b b 相差较大时，while循环次数将明显增多，显然也不是个高效的实现。

​ 蒙哥马利算法解决的是模乘运算的效率问题，即给定模数 n n n 和两个自然数 a , b < n a, b < n a,b