scheme - 为什么这个 Scheme 中的 Miller-Rabin Procedure 在代码看似错误的情况下却能正常工作？

Question

我正在通过 SICP 工作。在关于 Miller-Rabin 测试的练习 1.28 中。我有这段代码，我知道它是错误的，因为它不遵循练习的说明。

(define (fast-prime? n times)           
  (define (even? x)             
    (= (remainder x 2) 0))          
  (define (miller-rabin-test n)         
    (try-it (+ 1 (random (- n 1)))))        
  (define (try-it a)                
    (= (expmod a (- n 1) n) 1))         
  (define (expmod base exp m)           
    (cond ((= exp 0) 1) 
      ((even? exp)              
       (if (and (not (= exp (- m 1))) (= (remainder (square exp) m) 1)) 
         0
         (remainder (square (expmod base (/ exp 2) m)) m)))
      (else         
        (remainder (* base (expmod base (- exp 1) m)) m))))
  (cond ((= times 0) true)          
    ((miller-rabin-test n) (fast-prime? n (- times 1))) 
    (else false)))              

我在其中测试指数的平方是否等于 1 mod n。根据哪个根据我所阅读的内容，我看到的其他正确实现是错误的。我应该测试整个数字如下:

...
        (square 
         (trivial-test (expmod base (/ exp 2) m) m))
...

问题是我已经用许多质数和大的 Carmicheal 数测试过这个，它似乎给出了正确的答案，虽然有点慢。我不明白为什么会这样似乎工作。

Answer 1

您的函数版本“有效”只是因为您很幸运。试试这个实验:评估 (fast-prime? 561 3) 一百次。根据您的函数选择的随机见证，有时它会返回 true，有时它会返回 false。当我这样做时，我得到了 12 个 true 和 88 个 false，但您可能会得到不同的结果，具体取决于您的随机数生成器。

> (let loop ((k 0) (t 0) (f 0))
    (if (= k 100) (values t f)
      (if (fast-prime? 561 3)
          (loop (+ k 1) (+ t 1) f)
          (loop (+ k 1) t (+ f 1)))))
12
88

我面前没有 SICP——我的副本在家里——但我可以告诉你执行 Miller-Rabin 素性检验的正确方法。

您的expmod 函数不正确；没有理由对指数进行平方。这是执行模幂运算的正确函数:

(define (expm b e m) ; modular exponentiation
  (let loop ((b b) (e e) (x 1))
    (if (zero? e) x
      (loop (modulo (* b b) m) (quotient e 2)
            (if (odd? e) (modulo (* b x) m) x)))))

然后是 Gary Miller 的强伪素数检验，它是你的try-it 检验的强版本，它有一个证人 a 证明每个组合的组合 < em>n，看起来像这样:

(define (strong-pseudoprime? n a) ; strong pseudoprime base a
  (let loop ((r 0) (s (- n 1)))
    (if (even? s) (loop (+ r 1) (/ s 2))
      (if (= (expm a s n) 1) #t
        (let loop ((r r) (s s))
          (cond ((zero? r) #f)
                ((= (expm a s n) (- n 1)) #t)
                (else (loop (- r 1) (* s 2)))))))))

假设扩展黎曼假设，测试从 2 到 n-1 的每个 a 将证明(一个实际的、确定性的证明，而不仅仅是对素数的概率估计)质数 n 的素数，或确定至少一个 a 是复合 n 复合性的见证。 Michael Rabin 证明，如果 n 是复合的，则从 2 到 n-1 的 a 中至少有四分之三证明了该复合性，因此测试 k 随机碱基证明但不能证明素数 n 的素数概率为 4^−k。因此，这个 Miller-Rabin 素数测试的实现:

(define (prime? n k)
  (let loop ((k k))
    (cond ((zero? k) #t)
          ((not (strong-pseudoprime? n (random (+ 2 (- n 3))))) #f)
          (else (loop (- k 1))))))

这总是能正常工作:

> (let loop ((k 0) (t 0) (f 0))
    (if (= k 100) (values t f)
      (if (prime? 561 3)
          (loop (+ k 1) (+ t 1) f)
          (loop (+ k 1) t (+ f 1)))))
0
100

我知道您的目的是学习 SICP 而不是编写素数测试程序，但如果您对使用素数进行编程感兴趣，我谦虚地推荐 this essay在我的博客上，其中讨论了 Miller-Rabin 测试以及其他主题。您还应该知道，有比随机 Miller-Rabin 更好(更快、更不可能报告错误结果)的素数检验。