Square and Multiply

在密码学中经常看到a^b mod n运算，当b很大的时候，就不能够按照简单的数学运算进行了。

“Square and Multiply”就是一种窍门。

把指数转换成2进制，从左到右开始计算

  • 当指数二进制为1时 z^2*a mod n
  • 当指数二进制为0时 z^2 mod n

其中z为上一个指数二进制计算结果(从左到右)，初始为1

举例a^b mod 21 = 3^11 mod 21 = 3^1011 mod 21

  • z = 1
  • z = z^2*a = 1^2 * 3 mod 21 =
…