在密码学中经常看到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 = 3
- z = z^2 mod n = 3^2 mod 21 = 9
- z = z^2 mod n = 9^2 * 3 mod 21 = 12
- z= z^2 *a mod n = 12^2 * 3 mod 21 = 12
所以最终结果:3^11 mod 21 = 12
当然这种方式也存在一些安全问题 – Power consumption of an RSA decryption
Reference
- https://scientia-potentia-est.com/zh/square-multiply-algorithm/
Square and Multiply