आरयू '- एनएन' = को हल करने के लिए यूक्लिडियन एल्गोरिदम = 1. मोंटगोमेरी एल्गोरिदम के साथ मॉड्यूलर एक्सपोनिएंशन पाइथन या पेटीट चेज़ योजना

Question

में फर्मेट टेस्ट को कार्यान्वित करने के लिए मॉड्यूलर एक्सपोनेंटिएशन यह मेरी प्रारंभिक प्रोग्रामिंग कक्षा में योजना का उपयोग करके सिखाई गई व्यक्तिगत चुनौती है, लेकिन मैं समान रूप से समान होगा पायथन उदाहरणों से खुश

मैं पहले से ही इस योजना में मॉड्यूलर घातांक की बाइनरी पद्धति लागू इस प्रकार है:

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

रूप Chez योजना किसी भी कार्यान्वयन अजगर के पॉव (आधार एक्सपो Modu) के समान नहीं है यह आवश्यक है।

अब मैं मॉड्यूलर गुणा को हल करने के मोंटगोमेरी विधि को लागू करने की कोशिश कर रहा हूं। उदाहरण के लिए, मेरे पास है:

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 

मैं आरआर हल करने के लिए कैसे को समझने के लिए कोशिश कर रहा हूँ '- एनएन' = 1. मुझे लगता है कि आर के जवाब '64 होना चाहिए और एन' 81 होना चाहिए, लेकिन इस उत्तर को प्राप्त करने के लिए यूक्लिडियन एल्गोरिदम का उपयोग करने के तरीके को समझ में नहीं आता है।

Answer 1

बढ़ाया इयूक्लिडियन एल्गोरिथ्म है:

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

इस प्रकार, अपने उदाहरण पर,

> (euclid 79 100) 
19 
-15 
1 

आप my blog में और अधिक पढ़ सकते हैं।