Algoritmo euclideo per la risoluzione RR '- NN' = 1. Esponenziamento modulare con algoritmo Montgomery per implementare il test Fermat nello schema Python o Petite Chez

Question

Questa è una sfida personale nella mia classe introduttiva di programmazione insegnata con Scheme, ma vorrei essere ugualmente felice con gli esempi di Python.

ho già implementato il metodo binario di elevamento a potenza modulare in programma come segue:

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

Ciò è necessario in quanto Chez Scheme non ha alcuna implementazione simile a pow (expo modu base) di pitone.

Ora sto cercando di implementare il metodo Montgomery per risolvere la moltiplicazione modulare. Per fare un esempio, ho:

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 

Sto cercando di capire come risolvere RR '- NN' = 1. Mi rendo conto che la risposta a R 'dovrebbe essere 64 e N' dovrebbe essere 81, ma non capisco come usare l'algoritmo euclideo per ottenere questa risposta.

Answer 1

L'algoritmo di Euclide esteso è:

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

Così, il vostro esempio,

> (euclid 79 100) 
19 
-15 
1 

Si può leggere di più a my blog.