《密码技术与物联网安全：mbedtls开发实战》 —3.3.5　模重复平方

3.3.5　模重复平方

模算术运算中经常会计算大整数的幂运算，例如对于大整数m和大整数n，计算

bn mod m，通常可对b递归进行n-1次幂运算：

bn≡(bn-1(mod m))·b(mod m)

这样递归计算的效率通常较低，在实际应用中可通过模重复平方算法提高计算效率。下面通过一个具体示例说明模重复平方算法。

例3-4

通过计算137  mod 15来验证模算术运算中的幂运算。若按照一般的计算顺序，先计算137=62748517，然后再计算62748517 mod 15=7，在这种情况下需要7次乘法运算和一次模运算。本示例先把137分解为137=134×132×131，然后依次计算131、132和134。

第一步：计算131 mod 15

131 ≡ 13 mod 15

第二步：计算132 mod 15

132 ≡ 169 ≡ 4 mod 15

第三步：计算134 mod 15

134 mod 15的结果可由132 ≡ 4 mod 15间接获取，通过这种方法可大大减少计算量。

134 ≡ (132)2≡(4)2≡16≡1 mod 15

第四步：计算137=134×132×131 mod 15

137 ≡ 134×132×131≡1×4×13≡52≡7 mod 15

这种不直接计算137而通过中间结果计算137 mod 15的方法称为模重复平方算法，通过这种方法可以降低计算复杂度，缩短计算时间。