Euklidischer Algorithmus zum Lösen von RR '- NN' = 1. Modulare Exponentiation mit Montgomery-Algorithmus zur Implementierung von Fermat-Test in Python oder Petite Chez Schema

Question

Dies ist eine persönliche Herausforderung in meiner einführenden Programmierklasse unter Verwendung von Scheme, aber ich wäre gleichermaßen glücklich mit Python-Beispielen.

Ich habe bereits implementiert, um die binäre Methode des modularen Potenzierung in Schema wie folgt:

(define (pow base expo modu) 
    (if (zero? expo) 
     1 
     (if (even? expo) 
      (mod (expt (pow base (/ expo 2) modu) 2) modu) 
      (mod (* base (pow base (sub1 expo) modu)) modu)))) 

Dies ist notwendig, da Chez Scheme ähnlich jede Implementierung von Python pow (Basis expo modu) nicht.

Jetzt versuche ich die Montgomery-Methode zur Lösung der modularen Multiplikation zu implementieren. Als Beispiel habe ich:

Trying to solve: 
    (a * b) % N 
N = 79 
a = 61 
b = 5 
R = 100 
a' = (61 * 100) % 79 = 17 
b' = (5 * 100) % 79 = 26 
RR' - NN' = 1 

Ich versuche, wie zu verstehen RR zu lösen ‚- NN‘ = 1. Ich weiß, dass die Antwort auf R ‚64 sein sollte und N‘ 81 sein sollte, aber verstehe nicht, wie man den euklidischen Algorithmus benutzt, um diese Antwort zu erhalten.

Answer 1

Der erweiterte euklidische Algorithmus ist:

(define (euclid x y) 
    (let loop ((a 1) (b 0) (g x) (u 0) (v 1) (w y)) 
    (if (zero? w) (values a b g) 
     (let ((q (quotient g w))) 
     (loop u v w (- a (* q u)) (- b (* q v)) (- g (* q w))))))) 

So auf Ihrem Beispiel

> (euclid 79 100) 
19 
-15 
1 

Sie können mehr bei my blog lesen.