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

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

先上幂运算代码(clisp)：

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

运行结果

* (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)：

;;;; 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 $