Miller-Rabin Scheme實現不可預知的輸出

Question

我是Scheme的新手。我嘗試並使用PLT方案實施Rabin-Miller算法的概率變體。我知道這是隨機的，但大部分時間我都會得到錯誤的結果。我用C實現了相同的功能，並且它運行良好（從未嘗試失敗）。我在調試時得到了預期的輸出，但是當我運行時，它幾乎總是返回錯誤的結果。我使用了Wikipedia的算法。

(define expmod(lambda(b e m) 
       ;(define result 1) 
       (define r 1) 
       (let loop() 
        (if (bitwise-and e 1) 
         (set! r (remainder (* r b) m))) 
        (set! e (arithmetic-shift e -1)) 
        (set! b (remainder (* b b) m)) 
        (if (> e 0) 
         (loop)))r)) 

(define rab_mil(lambda(n k) 
        (call/cc (lambda(breakout) 
        (define s 0) 
        (define d 0) 
        (define a 0) 
        (define n1 (- n 1)) 
        (define x 0)   
        (let loop((count 0)) 
        (if (=(remainder n1 2) 0) 
         (begin 
          (set! count (+ count 1)) 
          (set! s count) 
          (set! n1 (/ n1 2)) 
          (loop count)) 
         (set! d n1))) 
        (let loop((count k)) 
        (set! a (random (- n 3))) 
        (set! a (+ a 2)) 
        (set! x (expmod a d n)) 
        (set! count (- count 1)) 

        (if (or (= x 1) (= x (- n 1))) 
         (begin 
          (if (> count 0)(loop count)))) 
        (let innerloop((r 0)) 
         (set! r (+ r 1)) 
         (if (< r (- s 1)) (innerloop r)) 
         (set! x (expmod x 2 n)) 
         (if (= x 1) 
          (begin 
          (breakout #f))) 
         (if (= x (- n 1)) 
          (if (> count 0)(loop count))) 
        ) 
        (if (= x (- s 1)) 
         (breakout #f))(if (> count 0) (loop count)))#t)))) 

另外，我的計劃是正確的方式嗎？ （我不知道關於突破環路部分，我使用call/cc，我發現它在一些網站，並從那以後一直使用它。）

在此先感謝。

Answer 1

一般而言，您正在以過於「必要」的方式進行編程;一個更優雅的expmod將是

(define (expmod b e m) 
    (define (emod b e) 
    (case ((= e 1) (remainder b m)) 
      ((= (remainder e 2) 1) 
      (remainder (* b (emod b (- e 1))) m) 
      (else (emod (remainder (* b b) m) (/ e 2))))))) 
    (emod b e)) 

它避免了使用set！和公正的遞歸執行規則

b^1 == b (mod m)  
b^k == b b^(k-1) (mod m) [k odd] 
b^(2k) == (b^2)^k (mod m) 

同樣的事情rab_mil在一個非常不時尚方案編程。這是一個替代實現。請注意，循環沒有'破壞'並且沒有調用/ cc;取而代之的是分段實現爲真正對應於Scheme中的'goto'的尾遞歸調用：

(define (rab_mil n k) 
    ;; calculate the number 2 appears as factor of 'n' 
    (define (twos-powers n) 
    (if (= (remainder n 2) 0) 
     (+ 1 (twos-powers (/ n 2))) 
     0)) 
    ;; factor n to 2^s * d where d is odd: 
    (let* ((s (twos-powers n 0)) 
     (d (/ n (expt 2 s)))) 
    ;; outer loop 
    (define (loop k) 
     (define (next) (loop (- k 1))) 
     (if (= k 0) 'probably-prime 
      (let* ((a (+ 2 (random (- n 2)))) 
       (x (expmod a d n))) 
      (if (or (= x 1) (= x (- n 1))) 
       (next) 
       (inner x next)))))) 
    ;; inner loop 
    (define (inner x next) 
     (define (i r x) 
     (if (= r s) (next) 
      (let ((x (expmod x 2 n))) 
       (case ((= x 1) 'composite) 
        ((= x (- n 1)) (next)) 
        (else (i (+ 1 r) x)))) 
     (i 1 x)) 
    ;; run the algorithm 
    (loop k)))