Miller-Rabin 测试的代码是否错误？ （SICP 1.28 练习的答案）
Is this code for Miller-Rabin test wrong? (answer for the exercise for 1.28 in SICP)
我正在尝试解决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。
这就是它应该做的。过程 expmod 应该计算一个数对另一个数的模的指数，这次唯一的区别是每次递归时都要检查一个非平凡的平方根。 m 将在 expmod 过程中保持不变，而您编写的 miller-rabin 过程将每次 运行 expmod 随机数 m。
编码愉快！
顺便说一下，祝 SICP 好运！我现在正在练习 2.45，它变得更容易了（尽管有一些非常抽象的概念）。
我正在尝试解决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。
这就是它应该做的。过程 expmod 应该计算一个数对另一个数的模的指数，这次唯一的区别是每次递归时都要检查一个非平凡的平方根。 m 将在 expmod 过程中保持不变，而您编写的 miller-rabin 过程将每次 运行 expmod 随机数 m。
编码愉快！
顺便说一下，祝 SICP 好运！我现在正在练习 2.45，它变得更容易了（尽管有一些非常抽象的概念）。