爲什麼Miller-Rabin Procedure在Scheme中工作時代碼看起來是錯的？

Question

我正在通過SICP工作。關於米勒 - 拉賓測試的練習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)) 
... 

的事情是，我已經測試了這一點，有許多素數和大僞素數， 它似乎給出正確的答案，雖然有點慢。我不明白爲什麼這個 似乎工作。

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在我面前 - 我的副本是在家裏 - 但是我可以告訴你執行米勒 - 拉賓檢驗的正確途徑。

您的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))))) 

然後加里·米勒的強僞素數測試，這是你的try-it測試的一個強有力的版本，其中有一個目擊者一個來證明每一個複合的compositeness ñ，看起來是這樣的：

(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至ñ -1將證明（實際的確定性證明，而不僅僅是素數的概率估計）素數的素數，或者確定至少一個，這是證明覆合的複合性n 。邁克爾·拉賓證明，如果ñ是從2的複合材料，至少四分之三ň -1證人到compositeness，所以測試ķ隨機基底演示，但並不能證明，該質數n的概率爲4 ^{− k}。因此，這個實現的米勒 - 拉賓檢驗的：

(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有更好的（更快，更不可能報告錯誤的結果）可用的素性測試。

Answer 2

在我看來，你仍然得到了正確的答案，因爲在expmod的每次迭代中，你檢查以前迭代的條件。您可以嘗試使用中的display函數調試exp值。真的，你的代碼與this one沒有太大的區別。