幂模运算快速算法——滑动窗口算法
设e 的二进制表达式为：∑-==
10)2(k i i i e e ，其中}1,0{∈i e 。

那么，n X e mod 的幂模运算二进制算法如下：
输入：X ，e ，n
输出：n X C e
mod =
Step 1: 1=C
Step 2: for 1-=k i downto 0
Step 2.1: n C C C mod )*(=
Step 2.2: if 1=i e then n X C C mod )*(=
Step 3: return C
由二进制法的计算过程可知：当指数e 的二进制位为0时，会减少乘模的次数。

二进制法的直接推广是m 进制法，其基本思想是把指数分成r bits(即m 2log bits)的数据块，每次取指数e 的r bits 进行运算，从而使整个幂模运算的效率提高。

假定e 的每个比特是0或1的概率相同，则m 进制法一个数据块是全0的可能性为r -2，当r 增加时，数据块为全0的可能性会减少，因此在Step 2.2需做乘模的可能性增加；而当r 减小时，算法总的乘模次数也会增加。

滑动窗口技术提供了一种折衷，允许零数据块和非零数据块是变长的，目的是增加全0数据块的数量，从而使总的乘模次数减少。

具体方法是：把k bits 指数分解成z 个零窗口或非零窗口i F ，i F 长度为)(i F L 。

规定最大窗口长度为d ，即))(max(i F L d =，显然总窗口数z 可能不等于d k 。

d 的取值与模数的位长有关。

对单一窗口的幂模运算进行预处理，即预计算n X w mod ，其中
12,,7,5,3-=d w ，因为指数分解的原则使非零窗口的最低有效位必定为1，故w 为为奇数，从而使预处理次数减少了一半。

滑动窗口算法处理幂模运算的过程如下：
输入：X ，e ，n
输出：n X C e mod =
Step 1: 预计算。

Step 2: 将k bits 的指数e 分解成长度为)(i F L 的零窗口或非零窗口i F ，1,,2,1,0-=z i 。

Step 3: 1=C
Step 4: for 1-=z i downto 0
Step 4.1: n C C i F L mod )(2=
Step 4.2: if 0≠i F then n X C C i F mod )*(=
Step 5: return C
窗口的划分采用了从左至右扫描的变长滑动窗口技术，因为计算是从高位至低位进行的。

如果采用从
右至左扫描的变长滑动窗口技术虽然可以使零窗口的数量有所增加，但它存在一个增加开销的缺点——需要记录各窗口的大小，而从左至右扫描则恰好相反。