Thuật toán Euclide để giải quyết RR '- NN' = 1. Mô tả lũy thừa với thuật toán Montgomery để thực hiện phép thử Fermat trong sơ đồ python hoặc Petite Chez

Question

Đây là một thách thức cá nhân trong lớp lập trình giới thiệu của tôi được dạy bằng cách sử dụng Đề án, nhưng tôi sẽ bằng nhau hài lòng với các ví dụ Python.

Tôi đã thực hiện phương pháp nhị phân của lũy thừa modulo trong chương trình như sau:

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

này là cần thiết như Chez Scheme không có bất kỳ thực hiện tương tự như pow (hội chợ Modu cơ sở) của python.

Bây giờ tôi đang cố gắng triển khai phương pháp giải quyết mô đun nhân của Montgomery. Ví dụ: Tôi có:

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 

Tôi đang cố gắng hiểu cách giải quyết RR '- NN' = 1. Tôi nhận thấy câu trả lời cho R 'phải là 64 và N' phải là 81, nhưng không hiểu cách sử dụng thuật toán Euclide để có được câu trả lời này.

Answer 1

Thuật toán Euclide mở rộng là:

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

Như vậy, trên ví dụ của bạn,

> (euclid 79 100) 
19 
-15 
1 

Bạn có thể đọc thêm tại my blog.