गणना करने के लिए सबसे तेज़ एल्गोरिदम (एक^(2^एन))% मीटर?

Question

मॉड्यूलर एक्सपोनेंटिएशन (ए^बी)% सी (जैसे राइट-टू-बाएं बाइनरी विधि की तरह: http://en.wikipedia.org/wiki/Modular_exponentiation) की गणना करने के लिए क्रिप्टोग्राफी के लिए जाने-माने एल्गोरिदम हैं।

लेकिन क्या एल्गोरिदम फॉर्म के मॉड्यूलर एक्सपोनेंटिएशन (ए^(2^एन))% m की गणना करने के लिए "क्लासिकल" एल्गोरिदम के मुकाबले तेजी से है?

बहुत बहुत धन्यवाद!

नोट:

1) मीटर एक बहुत बड़ी प्रधानमंत्री हो सकता है ... या नहीं (ताकि मीटर के आधार पर कोई अनुकूलन)

2) एन के रूप में बड़ा हो सकता है 2^32-1 (एन < 2^32)

Answer 1

यदि एम प्रमुख है, तो आप इसे बहुत तेज़ी से गणना कर सकते हैं।

आप पी = 2 ^एन% (एम -1) के दाएं से बाएं बाइनरी विधि के साथ कंप्यूटिंग के साथ शुरू करते हैं।

तो फिर तुम एक ^पी% मीटर है, जो Fermat's little theorem की वजह से मूल अभिव्यक्ति के बराबर है गणना करने के लिए सही-से-बाएँ बाइनरी पद्धति का उपयोग।

---

तो मीटर प्रधानमंत्री, लेकिन काफी छोटा नहीं है, इतना है कि यह कारक किया जा सकता है, तो आप यूलर totient समारोह की गणना और Euler's Theorem उपयोग कर सकते हैं।

यदि एम के आधार पर कोई अनुकूलन संभव नहीं है, तो शायद आप सबसे अच्छा कर सकते हैं Montgomery reduction का उपयोग कर रहा है।

Answer 2

इसके अलावा, एव्जेनी के जवाब देने के लिए एक सामान्यीकरण के रूप में: यदि आप मीटर की गुणन पता: m = p1 * p2 * ... * p{n}, आप Euler's theorem उपयोग कर सकते हैं:

totient phi(m)= (p1-1)*(p2-1)*...*(p{n}-1) की गणना।

फिर आप p = 2^N % phi(m) पर गणना कर सकते हैं और a^(2^N) % m = a^p % m देख सकते हैं।

इनमें से कोई भी 2^N के विशेष रूप का उपयोग नहीं करता है।

Answer 3

Evgeny और Rasmus महान उत्तर देते हैं। उसमें जोड़ने के लिए, शक्तियों के लिए लगातार स्क्वायरिंग का उपयोग करना याद रखें। यही कारण है कि है, प्रतिपादक लिखते हैं, E कहते हैं, आधार 2 में:

E = b0*1 + b1*2 + ... + bk*2^k 

या तो 0 या 1 और bk = 1 पिछले अशून्य सा है जहां प्रत्येक bi है।तो फिर तुम एक नंबर N, प्रतिपादक E को

N^E (mod m) = n0^b0 * n1^b1 * ... * nk^bk (mod m) 

द्वारा जहां

n0 = N (mod m) 
n1 = n0^2 (mod m) 
n2 = n1^2 (mod m) 
... 
nk = n(k-1)^k (mod m) 

उदाहरण के लिए, गणना करने के लिए 28^27 mod 76 बढ़ा, कह सकते हैं, आप N = 28, E = 27, m = 76 है, और गणना

है

27 = 1 + 2 + 8 + 16 
E = b0 + b1 + b3 + b4 

और

n0 = 28 (mod 76) 
n1 = 28^2 (mod 76) = 24 
n2 = 24^2 (mod 76) = 44 
n3 = 44^2 (mod 76) = 36 
n4 = 36^3 (mod 76) = 4 

और अंत में

28^27 (mod 76) = 28 * 24 * 36 * 4 (mod 76) = 20 
N^ E (mod m) = n0 * n1 * n3 * n4 (mod 76)