Miller-Rabin Scheme 구현 예기치 않은 결과

Question

나는 Scheme을 처음 사용합니다. PLT Scheme을 사용하여 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)))) 

또한 Scheme에서 올바르게 프로그래밍하고 있습니까? (나는 루프 부분에서 내가 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)) 

집합의 사용을 피하는! 재귀 적으로 규칙을 구현한다.

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

마찬가지로 rab_mil은 매우 비 체계적으로 프로그래밍된다. 다음은 대안 구현입니다. 루프가 끊어지지 않고 call/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)))