我们从一个简单的问题开始。 $ 6^{208}\%23 $等于多少。解这个题目最笨的方法是把$6^{208}$算出来,然后再算$6^{208}\%23$。接下来我们讲解一种快速计算的方法。此方法在ACM-ICPC中非常重要,在密码学考试中一样相当重要。

首先我们来计算一下$6^{208}$是多少吧。

先上幂运算代码(clisp):

1
2
3
4
(defun pow (x n)
(if (= n 0)
1
(* x (pow x (1- n)))))

运行结果

1
2
3
4
5
6
7
8
9
10
11
12
* (defun pow (x n)
(if (= n 0)
1
(* x (pow x (1- n)))))

POW
* (pow 6 208)

716902475118262214817011779393196661223001384517326117611478588644678638278414107572257870390965072733283553862876694482148415089417201250632070732438043011055616
* (mod (pow 6 208) 23)

4

接下来上快速幂代码(clisp):

1
2
3
4
5
6
7
8
9
10
11
12
;;;; pow_mod function
(defun pow_mod (x n mod_value)
(if (= n 0)
1
(if (= n 1)
(mod x mod_value)
(mod
(*
(mod (pow (pow_mod x (floor (/ n 2)) mod_value) 2) mod_value)
(pow_mod x (mod n 2) mod_value)
)
mod_value))))

最后计算出来等于4

那么接下来在说快速幂之前我们先讲一个公式: $ (a \times b) \% n = [ (a \% n) \times (b \% n) ] \% n $