2.7.2　快速模幕运算

幂运算非常简单，很容易计算。比如计算，可以列出，只需要计算15次乘法就能得到答案。但是如果指数是一个大数，比如1000000000 ，那么求这种高次幂的最小正整数模应该怎么办呢？对于这种大数，挨个计算就太复杂了，会降低加解密的效率。为了提高效率，就必须想办法在计算的过程中用最少的步骤来快速达到指定的指数。

想快速得到幂运算的结果就需要用到二进制。当指数使用二进制表示时，只有0和1可以作为系数出现，这意味着每个正整数都可以表示为2的不同幂的和。还是以为例，十进制转二进制的方法如例1.3.1所示。利用平方，可以快速得到结果：

仅需4次计算就能得到结果。相比进行15次重复运算，大大节约了时间。

如果幂不是2的倍数呢？比如，应该如何计算？其实也很简单，拆分计算即可：

这样也仅需6次就可以得到答案。

例2.7.3　上面例子的计算较简单，不使用相关公式也可以计算。如果是)这种大数模的幂运算呢？在通常的运算过程中人们都不想处理大数，因为这时候计算太繁琐。此时可应用幂取模运算的办法。

解：第1步，将中的指数转化为二进制数。

用Python代码可写成:

 1  #二进制数
 2  number = 2641
 3  number_bin = bin(number)[2:]
 4  cov_number_bin = bin(number)[2:][::-1]
 5
 6  sum_number = ''
 7  for i in range(len(cov_number_bin)):
 8      if cov_number_bin[i] == '1':
 9          if sum_number == '':
10              sum_number += str(2**(i))
11          else:
12              sum_number += ' + ' + str(2**(i))
13  print(sum_number)

第2步，用重复平方（Repeated Squaring）得到幂的余。

因为，因此，得到3278564后继续使用作为的基本单位。不用直接计算，只需要计算。得到1631541后又可以继续应用在上，使得。以此类推，以减少运算量，得到所有的2次幂项的余：

第3步，将第1步得到的幂次相乘。

Python计算过程如下，速度比Python的运算符快，因为无须重复计算。下面的函数等同于Python内置函数pow(a,n,p)。

 1  def fastExpMod(a, n, p):
 2      result = 1
 3      while n != 0:
 4          if (n&1) == 1:
 5              # ei = 1, then mul
 6              result = (result * a) % p
 7          n >>= 1
 8          # a, a^2, a^4, a^8, ... , a^(2^n)
 9          a = (a*a) % p
10      return result

因此，如果是正整数，计算的时间复杂度大约为。

欧拉定理除了可以用于快速求大数幂运算的模，还可以用于求逆元。当时，因为根据欧拉定理，同乘可以得到，等式两边调换一下位置得到：

如果为素数，那么就很容易得到：

例2.7.4　计算、。

解：计算。因为，且997是素数，所以：

计算。因为，所以可以用欧拉定理。但151255不是素数，所以需要计算。首先，因此可以很容易算出:

那么: