SICP練習1.28：Miller-Rabin測試中的假陰性

Question

練習1.28。費馬測試的一個不能被愚弄的變體稱爲米勒 - 拉賓測試（Miller 1976; Rabin 1980）。這個 從費馬小定理的另一種形式開始，它指出 如果n是質數並且a是小於n的任何正整數，那麼上升到（n-1）st次冪是一致的1模ñ。通過米勒 - 拉賓測試對 測試數n的素數，我們選取​​一個 隨機數a < n並使用expmod過程將a加到（n-1）st模n。然而，每當我們在expmod中執行平方步驟 時，我們檢查是否已經發現了一個「非平凡的正方形 根1模n」，即一個不等於1或n - 1的數，它的正方形爲 等於1模n。有可能證明如果存在這樣一個非平凡平方根1，那麼n不是素數。也可以用 來證明，如果n是不是素數的奇數，那麼至少有一半的數字爲<n，用這種方式計算^（n-1）將使得 揭示非平凡平方根以1爲模n。 （這就是爲什麼 米勒 - 拉賓測試不能被愚弄的原因。）修改expmod過程爲 信號，如果它發現1的平凡平方根並且使用它到 以類似於 的過程實施Miller-Rabin測試-測試。通過測試各種已知素數和非素數來檢查你的程序。提示：一個便捷的方式，使expmod信號是有 它返回0

(define (fast-prime? n) 
    (define (fast-prime-iter n counter) 
    (cond ((= counter 1) #t) ; There is no need to check 1 
      ((miller-rabin-test n counter) 
      (fast-prime-iter n (- counter 1))) 
      (else 
      (newline) 
      (display counter) 
      #f))) 
    (fast-prime-iter n (- n 2))) 

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

(define (nontrivial-square-root? val) 
    (if (= val 1) 
    0 
    val)) 

我的想法是過濾掉那些所謂的「1個模n的非平凡平方根」規定的程序nontrivial-square-root?。如果(remainder (square (expmod base (/ exp 2) m)) m)爲1，則返回0，在這種情況下，(expmod base (/ exp 2) m)的平方必須等於1模n（這是因爲m總是等於n），因此它是非平凡的平方根。

雖然nontrivial-square-root?確實篩選出卡邁克爾數字，如561,1105,1729,2465,2821和6601，但質數如7和13也被報告爲複合數據。

是什麼導致了這些假陰性？

Answer 1

報價的標有粗體字的重要組成部分：

但是，每當我們執行expmod的平方步驟，我們檢查，如果我們已經發現了1個模n的「」平凡的平方根「」那就是，一些不等於1或N - 1其平方等於1個模n

，因此，您廣場，走你必須檢查其餘的參數不是1或n - 1.發生這種情況，例如，如果您致電(miller-rabin-test 5 3)。通過遞歸處理，您會注意到有一個調用(nontrivial-square-root? (remainder (square 4) 5))，其計算結果爲(nontrivial-square-root? 1)。然而，5仍然可以是素數，因爲4是5-1。

因此，在平方部分，例如，，調用下面的函數：

(define (sqrmod-with-check val n) 
    (let ((sqrmod (remainder (square val) n))) 
    (cond ((or (= val (- n 1)) (= val 1)) sqrmod) 
      ((= sqrmod 1) 0) 
      (else sqrmod)))) 

這裏的參數是expmod通話和m。除了在我們找到1模n的非平凡平方根的情況下，它會爲你做平方和餘數。當它返回0時，我將它分成三個條件，而不是兩個，僅僅是因爲可讀性。