快速指数运算:平方-乘算法

RSA 加解密中存在指数运算 x^a。
通常解密运算中的 指数 非常大，a 的二进制位数 通常会大于等于1024 bit， 即 可能 a >=2^1024.

如果用一般方法直接计算 X^a的值， 即X*X*X......需要的运算量非常大


定义:    MUL       为乘法运算 即乘以x ，
         sq         为平方运算

考虑一个例子 计算x⁸
则最简单的方法需要8次乘法运算


而更快捷的方法只需要3次平方运算

在看一个更一般的例子，计算 X²⁴
最简单的方法就是计算24次乘法。

更有效的方法如下： 即一次平方操作，一次乘法操作(乘以x)，之后再三次平放操作。 即5次操作即可得到结果

也就是说对于指数运算 两种基本操作就可以得到结果：
    对当前结果平方
    当前结果与x相乘

问题是如何确定平方与乘法的执行顺序, 平方-乘算法就可以解决这个问题。

大致描述为： 对 X^a  将指数a 表示为2进制形式，高bit在左，然后从左至右扫描对应的bit位。除了最左边的bit（MSB）以外，在扫描之后每个bit位时对当前结果平方，如果该bit位为1，则需多进行一次 乘法操作

以计算 X²⁴为例：

X²⁴  将指数表示为 二进制形式  X¹¹⁰⁰⁰  表示为X^b1b2b3b4b5
开始扫描指数的每个Bit:         下面的红体表示数值为2进制表示

1:     初始值  x = x¹;                初始化设置，b1 = 1  ,扫描第一个bit时不需要做其他操作

2:      X² = X¹⁰                                  b2=1，先平方
         X² * X = X³ =X¹¹                         再乘以 X

3：   (X³)² = X⁶ = X¹¹⁰                    b3= 0，只需要一次平方

4:    (X⁶)²  = X¹² = X¹¹⁰⁰                 b4 = 0，只需要一次平方

5： (X¹²)² = X²⁴ = X¹¹⁰⁰⁰                b5 = 0,只需一次平方

通过观察运算过程中指数的二进制表示的变化能更好的理解算法，一次平方操作会让指数向左移一位，并在最右边添加0，
而与 X 相乘的操作即在指数的最右边位置上填上 1