Test de Miller-Rabin (SICP 1.28)

Question

Une variante du test de Fermat qui ne peut être trompée est appelée le test de Miller-Rabin (Miller 1976 ; Rabin 1980). Elle part d'une autre forme du petit théorème de Fermat, qui stipule que si n est un nombre premier et a est tout entier positif inférieur à n entonces a élevé au niveau de la (n - 1) Le pouvoir d'achat est congruent à 1 modulo n .

Pour tester la primalité d'un nombre n par le test de Miller-Rabin, nous choisissons un nombre aléatoire a moins de n et augmenter a à la (n - 1) puissance st modulo n en utilisant le expmod procédure. Cependant, chaque fois que nous effectuons l'étape de la mise au carré en expmod nous vérifions si nous avons découvert une "racine carrée non triviale de 1 modulo n c'est-à-dire un nombre qui n'est pas égal à 1 o n - 1 dont le carré est égal à 1 modulo n .

Il est possible de prouver que si une telle racine carrée non triviale de 1 existe, alors n n'est pas premier. Il est également possible de prouver que si n est un nombre impair qui n'est pas premier, alors, pour au moins la moitié des nombres a < n , informatique a n-1 de cette manière révélera une racine carrée non triviale de 1 modulo n . (C'est pourquoi le test de Miller-Rabin ne peut être trompé).

Modifier le expmod pour signaler s'il découvre une racine carrée non triviale de 1 et l'utiliser pour mettre en œuvre le test de Miller-Rabin avec une procédure analogue à celle de fermat-test . Vérifiez votre procédure en testant divers nombres premiers et non premiers connus. Astuce : Une façon pratique de faire des expmod est de lui faire renvoyer 0.

Voici ce que j'ai jusqu'à présent.

(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))

(define (expmod-signal b n m)
  (define (check a)
    (and (not (= a 1))
         (not (= a (- n 1)))
         (= (square a) (remainder 1 n))))
  (cond ((= n 0) 1)
        ((check b) 0)
        ((even? n) (remainder (square (expmod-signal b (/ n 2) m)) m))
        (else (remainder (* b (expmod-signal b (- n 1) m)) m))))

(define (miller-rabin n)
  (define (fail? n a)
    (or (= n 0) (not (= n a))))
  (define (try a)
    (cond ((= a 1) #t)
          ((fail? (expmod-signal a (- n 1) n) a) #f)
          (else (try (- a 1)))))
  (try (- n 1)))

Je pense avoir mis en œuvre miller-rabin correctement, mais je ne comprends pas comment la version modifiée de la expmod est censé fonctionner. Vérifie-t-on le nombre avant le carré ou après le carré ? Je ne le sais pas en lisant la question.

Answer 1

J'ai résolu ce problème en utilisant la définition originale de expmod à l'intérieur de expmod-signal . Quelque part dans mes tests, expmod-signal renvoyait naturellement zéro et perturbait les tests. J'ai mal compris la fonction de vérification, "dont le carré est égal à 1 modulo n" signifie vérifier si a^2 % m = 1 . Cette fonction de vérification renvoie 0 si l'argument est une racine carrée non triviale de 1 mod n, et renvoie l'argument dans le cas contraire. Si elle renvoie zéro, le zéro se propage à travers le reste de expmod-signal et est renvoyée.

(define (square x) (* x x))
(define (even? n) (= (remainder n 2)))

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
        (else (remainder (* base (expmod base (- exp 1) m)) m))))

(define (expmod-signal b n m)
  (define (check a)
    (if (and (not (= a 1))
             (not (= a (- n 1)))
             (= (remainder (square a) n) 1))
        0
        a))
  (cond ((= n 0) 1)
        ((even? n) (remainder (square (check (expmod b (/ n 2) m))) m))
        (else (remainder (* b (expmod b (- n 1) m)) m))))

(define (miller-rabin n)
  (define (fail? a)
    (or (= a 0) (not (= a 1))))
  (define (try a)
    (cond ((= a 1) #t)
          ((fail? (expmod-signal a (- n 1) n)) #f)
          (else (try (- a 1)))))
  (try (- n 1)))