从数学上讲，为什么这个 SICP 算法对一个数的指数模另一个数有效？

Question

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

作者声称它“计算一个数的指数modulo另一个数”。例如 (expmod 5 3 n) 应该 return (5^3) mod n.

但是，从数学的角度来看，我就是看不出它是如何工作的。正如 footnote 46 所强调的，它旨在使用属性，对于任何正整数 a、b 和 n，(ab) mod n = [(a mod n)(b mod n)] mod n，但我看不出它是如何实际使用它的。考虑 (expmod 5 3 3):

首先，我们调用(expmod 5 3 3)。从数学上讲，这意味着我们要求 (5^3) mod 3.
由于第二个参数是奇数，我们计算(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)modn=[(amodn)(bmodn)]modn形式, 所以它没有使用预期的属性.

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

Answer 1

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

也是如此。

这是 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

Answer 2

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

(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 整除，因此在执行外部 remainder 时将计算为 0，所以这相当于:

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

从数学上讲，为什么这个 SICP 算法对一个数的指数模另一个数有效？

Mathematically, why does this SICP algorithm for the exponent of a number modulo another number work?

scheme

sicp

exponentiation

modular-arithmetic