scheme - Miller-Rabin 测试的代码是否错误？ (SICP 1.28 练习的答案)

Question

我正在尝试解决 SICP 中关于 Miller-Rabin 算法的练习 1.28，之后我在网上找到了答案，但我认为答案是错误的。我来问问有没有错。

他在执行 expmod 循环时检查是否 (remainder (square base) m)=1。但是，在做循环的时候，base和m会一直保持不变，也就是说他在做同样的检查，这不是Miller-Rabin Test想要做的。

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

(define (nontrivial-square-root? a n)
  (and (not (= a 1))
       (not (= a (- n 1)))
       (= 1 (remainder (square a) n))))

如果 n=k*2^c，我认为我们应该检查 (remainder (a^(k*2*(c-1))) n)=1.

Answer 1

这就是它应该做的。过程 expmod 应该计算一个数对另一个数的模的指数，这次唯一的区别是每次递归时都要检查一个非平凡的平方根。 m 将在 expmod 过程中保持不变，您编写的 miller-rabin 过程将运行 expmod每次随机数m。

编码愉快!

顺便说一下，祝 SICP 好运!我现在正在练习 2.45，它变得更容易了(尽管有一些非常抽象的概念)。