Implémentation du schéma de Miller-Rabin sortie imprévisible

Question

Je suis nouveau à Scheme. J'ai essayé et mis en œuvre la variante probabiliste de l'algorithme de Rabin-Miller en utilisant PLT Scheme. Je sais que c'est probabiliste et tout, mais je reçois les mauvais résultats la plupart du temps. J'ai mis en œuvre la même chose en utilisant C, et cela a bien fonctionné (jamais échoué un essai). Je reçois la sortie attendue pendant le débogage, mais quand je cours, il revient presque toujours avec un résultat incorrect. J'ai utilisé l'algorithme de 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)))) 

De même, est-ce que je programme la bonne façon dans Scheme? (Je ne suis pas sûr de la rupture de la partie boucle où j'utilise call/cc. Je l'ai trouvé sur un site et l'utilise depuis.)

Merci d'avance.

Answer 1

En général, vous programmez de façon trop "impérative"; un expmod plus élégant serait

(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)) 

ce qui évite l'utilisation de l'ensemble! et juste met en œuvre les règles récursive

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

De même, la chose rab_mil est programmé de façon très non-système. Voici une implémentation alternative. Notez qu'il n'y a pas de "rupture" des boucles et pas d'appel/cc; Au lieu de cela, la rupture est implémentée comme un appel récursif en queue qui correspond vraiment à 'goto' dans le schéma:

(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)))