^^ बी मोड एम की गणना कैसे करें?

Question

मुझे ए, बी, एम < 2^32
के बड़े मूल्यों के लिए कुशलतापूर्वक ^^ बी मोड मीटर की गणना करना है, जहां ^^ टेट्रेशन ऑपरेटर है: 2 ^^ 4 = 2^(2^(2^2))

मीटर एक प्रमुख संख्या नहीं है और दस की शक्ति नहीं है।

क्या आप मदद कर सकते हैं?

Answer 1

स्पष्ट होने के लिए, ^^ बी^बी के समान नहीं है, यह घातीय टावर ए^(ए^(ए^...^ए) है) जहां बी की प्रतियां हैं, टेट्रेशन के रूप में भी जाना जाता है। चलो टी (ए, बी) = एक ^^ बी तो टी (ए, 1) = ए और टी (ए, बी) = ए^टी (ए, बी -1)।

टी (ए, बी) मॉड एम = ए^टी (ए, बी -1) मॉड एम की गणना करने के लिए, हम एक बहुत बड़े एक्सपोनेंट के साथ एक एम मीटर की शक्ति की गणना करना चाहते हैं। आप इसका उपयोग कैसे कर सकते हैं यह है कि मॉड्यूलर एक्सपोनेंटिएशन प्रीपेरियड लम्बाई है जो एम के प्रमुख कारक में प्राइम की सबसे बड़ी शक्ति है, जो कि अधिकांश लॉग_2 मीटर पर है, और अवधि की लंबाई फाई (एम) को विभाजित करती है, जहां फाई (एम) Euler's totient function है। वास्तव में, अवधि की लंबाई एम, लैम्ब्डा (एम) के Carmichael's function विभाजित करती है। तो,

a^k mod m = a^(k+phi(m)) mod m as long as k>log_2 m. 

(बाद में, फ़ाई (एम) के लिए, फ़ाई (phi (एम)), आदि या) ध्यान रहे कि एक जरूरी अपेक्षाकृत मीटर प्रधानमंत्री नहीं है रहो। यदि यह था, तो आप कह सकते हैं कि एक^के मोड एम = ए^(के मॉड फाई (एम)) मॉड एम। हालांकि, यह हमेशा सत्य नहीं होता है जब ए और एम अपेक्षाकृत प्रमुख नहीं होते हैं। उदाहरण के लिए, फाई (100) = 40, और 2^1 मॉड 100 = 2, लेकिन 2^41 मॉड 100 = 52. आप बड़े एक्सपोनेंट को कम संख्या में संशोधित कर सकते हैं mod phi (m) जो कम से कम log_2 m हैं, इसलिए आप कह सकते हैं कि 2^10001 मॉड 100 = 2^41 मॉड 100 लेकिन आप इसे 2^1 मॉड 100 तक कम नहीं कर सकते हैं। आप एक मॉड एम [न्यूनतम x] परिभाषित कर सकते हैं या न्यूनतम + मोड (ए-मिनट, एम) का उपयोग कर सकते हैं जब तक एक> मिनट।

टी (ए, बी -1)> [log_2 मीटर], तो

a^T(a,b-1) mod m = a^(T(a,b-1) mod phi(m) [minimum [log_2 m]]) 

अन्यथा सिर्फ एक^टी (ए, बी -1) आधुनिक मीटर की गणना करते हैं।

पुनरावर्ती रूप से इसकी गणना करें। आप lambda (एम) के साथ फाई (एम) को प्रतिस्थापित कर सकते हैं।

2^32 के तहत किसी संख्या के प्रमुख कारककरण की गणना करने में बहुत लंबा समय नहीं लगता है क्योंकि आप अधिकतम 2^16 = 65,536 परीक्षण प्रभागों में प्रमुख कारकों को निर्धारित कर सकते हैं। प्राइम फैक्टरेशन के मामले में फि-लैम्ब्डा जैसे संख्या-सैद्धांतिक कार्य आसानी से व्यक्त किए जाते हैं।

प्रत्येक चरण में, आपको छोटे एक्सपोनेंट्स के साथ मॉड्यूलर शक्तियों की गणना करने में सक्षम होना होगा।

आप शक्तियों की गणना कर रहे हैं फाई (एम), फिर शक्तियों मोड फाई (फाई (एम)), तो शक्तियों मोड फाई (फाई (फाई (एम)), आदि। यह कई पुनरावृत्तियों को नहीं लेता है पुनरावृत्त फाई फ़ंक्शन 1 से पहले है, जिसका अर्थ है कि आप सब कुछ 0 तक कम करते हैं, और अब आपको टावर की ऊंचाई बढ़ाने से कोई बदलाव नहीं मिलता है।

यहां एक उदाहरण है, जो हाई स्कूल गणित प्रतियोगिताओं में शामिल है, जहां प्रतियोगियों को इसे फिर से खोजना और हाथ से निष्पादित करना है। 14 ^^ 2016 के अंतिम दो अंक क्या हैं?

14^^2016 mod 100 
= 14^T(14,2015) mod 100 
= 14^(T(14,2015) mod lambda(100) [minimum 6]) mod 100 
= 14^(T(14,2015 mod 20 [minimum 6]) mod 100 

T(14,2015) mod 20 
= 14^T(14,2014) mod 20 
= 14^(T(14,2014) mod 4 [minimum 4]) mod 20 

T(14,2014) mod 4 
= 14^T(14,2013) mod 4 
= 14^(T(14,2013 mod 2 [minimum 2]) mod 4 

T(14,2013) mod 2 
= 14^T(14,2012) mod 2 
= 14^(T(14,2012 mod 1 [minimum 1]) mod 2 
= 14^(1) mod 2 
= 14 mod 2 
= 0 

T(14,2014) mod 4 
= 14^(0 mod 2 [minimum 2]) mod 4 
= 14^2 mod 4 
= 0 

T(14,2015) mod 20 
= 14^(0 mod 4 [minimum 4]) mod 20 
= 14^4 mod 20 
= 16 

T(14,2016) mod 100 
= 14^(16 mod 20 [minimum 6]) mod 100 
= 14^16 mod 100 
= 36 

तो, 14^14^14^...^14 अंकों में समाप्त होता है ... 36।