最近研究了下网易云音乐的登录机制，涉及到了RSA算法，最初在编写幂运算求模这部分时，直接先幂运算然后再求余，发现效率及其低下，但是由于common lisp里没有提供类似于powmod之类的函数，决定参考资料重写一个。
首先，这个问题用数学表示就是：求一个整数X的N次方除以某个整数P的余数。
用数学公式表示则如下：
经过研究，主要可以基于这两个推导公式写出：
(x * y) % p = (x * (y % p)) % p = ((x % p) * (y % p)) % p
(x ^ n) % p = ((x % p) ^ n) % p
(^ 表示幂运算， % 表示取余)
举例，
当n为偶数时：
x^n % m ==> (x^(n / 2))^2 % m ==> (x^(n / 2) % m)^2 % m
当n为奇数时：
x^n % m ==> (x * x^(n - 1)) % m ==> (x * (x^(n - 1) % m)) % m
最终，我们根据这种思路，可以得出如下递归方式的代码：
(defun square (x)
(* x x))
(defun expt-mod (base exponent modulus)
(if (= exponent 0)
1
(if (evenp exponent)
(mod (square (expt-mod base (/ exponent 2) modulus)) modulus)
(mod (* base (expt-mod base (- exponent 1) modulus)) modulus))))
