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)
:
(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) mod n = [ (a mod n)(b mod n)] mod n 形式,因此无法使用预期的属性。那么,鉴于这似乎没有使用预期的属性,为什么这个算法有效?我忽略了模运算的哪些属性?
这是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
整除,因此在执行外部
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
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