从数学上来说，为什么这个 SICP 算法可以对一个数以另一个数取模的指数起作用？

Question

SICP第 1.2.6 节给出了以下程序：

    (define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

作者声称它“计算一个数字对另一个数字取模的指数”。例如 (expmod 5 3 n)

 应返回 (5^3) mod n。

但是，从数学的角度来看，我只是看不出它是如何工作的。正如

脚注 46 所强调的那样，它的目的是使用以下属性：对于任何正整数 a、b 和 n，(ab) mod n = [(a mod n)(b mod n)] mod n，但我无法看到它实际上是如何使用它的。考虑(expmod 5 3 3)

：

首先，我们调用
1. (expmod 5 3 3)

   。从数学上讲，这意味着我们要求 (5^3) mod 3。

由于第二个参数是奇数，我们计算
2. (remainder (* 5 (expmod 5 (- 3 1) 3)) 3)

    即 

   (remainder (* 5 (expmod 5 2 3)) 3)

   。从数学上讲，这是 [5 * [(5^2) mod 3]] mod 3。由于该表达式中的初始 5 没有附加 mod 3，因此该表达式在 (ab) mod n = [ (a mod n)(b mod n)] mod n 形式，因此无法使用预期的属性。

   那么，鉴于这似乎没有使用预期的属性，为什么这个算法有效？我忽略了模运算的哪些属性？

这是1.2.4中fast-exp的定义，参考：

Answer 1

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

如果我们将其重命名为更匹配 expmod，它看起来像这样：

(define (expt base exp)
  (cond ((= exp 0) 1)
        ((even? exp)
         (square (expt base (/ exp 2))))
        (else
         (* base (expt base (- exp 1))))))

为了得到一个简单的

expmod

，我们现在可以只计算每个子句的余数：

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expt base (/ exp 2))) m))
        (else
         (remainder (* base (expt base (- exp 1))) m))

到目前为止我们还没有使用脚注

(ab) mod m = ((a mod m)(b mod m) mod m)

。 当然，一个特殊情况是

(aa) mod m = ((a mod m)(a mod m) mod m)

，它给出 

(remainder (square a) m) = (remainder (sqaure (remainder a m)) m)

。  我们可以将其与 

even

 子句一起使用，这样

         (remainder (square (expt base (/ exp 2))) m)

变成：

         (remainder (square (remainder (expt base (/ exp 2)) m))
                    m)

在这中间我们有指数的余数，所以这相当于： (remainder (square (expmod base (/ exp 2) m)) m)

使用新的

even

子句，我们有

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m)) 
                    m))
        (else
         (remainder (* base (expt base (- exp 1))) m))

为了简化奇怪的子句，我们现在使用

E

代替

(expt base (- exp 1))

。

通过使用 

mod

的定义属性，我们可以说对于任何数字

a

:

         a = (+ (* (quotient a m) m) (remainder a m))

所以这也是事实： E = (+ (* (quotient E m) m) (remainder E m))

将其代入我们的

odd

子句中：

         (remainder (* base E) m)

给出： (remainder (* base (+ (* (quotient E m) m) (remainder E m))) m)

我们可以忽略

(* (quotient E m) m)

，因为任何包含它的项都可以被

m

整除，因此在执行外部

0

时将评估为

remainder

，所以这相当于：

         (remainder (* base (remainder E m)) m)

将 E 扩展到其原始值： (remainder (* base (remainder (expt base (- exp 1)) m)) m)

再一次，在中间，我们有指数的余数，所以这变成： (remainder (* base (expmod base (- exp 1) m)) m)

我们的

expmod

现在是：

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m)) 
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

(ab) mod n = [a (b mod n)] mod n

Answer 2

也是如此。这是

a

上的归纳证明。

基本情况：当 

a = 0

、

(0b) mod n = 0 mod n = [0 (b mod n)] mod n

时。

感应案例：

通过归纳假设，假设

(ab) mod n = [a (b mod n)] mod n

为真。我们需要证明这一点

((a+1) b) mod n = [(a + 1) (b mod n)] mod n

。

((a+1) b) mod n
= (ab + b) mod n
= (ab mod n) + (b mod n)
= [a (b mod n)] mod n + (b mod n)             by induction hypothesis
= [a (b mod n)] mod n + (b mod n) mod n
= [a (b mod n) + (b mod n)] mod n
= [(a + 1) (b mod n)] mod n

随心所欲。这就证明了

(ab) mod n = [a (b mod n)] mod n

其实你也能看到

---

(ab) mod n = [(a mod n) (b mod n)] mod n

是由此得出的结果。证明如下：

(ab) mod n 
= [a (b mod n)] mod n            by what we just proved
= [(b mod n) a] mod n
= [(b mod n) (a mod n)] mod n    by what we just proved
= [(a mod n) (b mod n)] mod n