पायथन

Question

में बहुत बड़े एक्सपोनेंट की गणना करना वर्तमान में मैं इसका परीक्षण करने के लिए अपनी क्रिप्टोग्राफिक योजना का अनुकरण कर रहा हूं। मैंने कोड विकसित किया है लेकिन मैं एक बिंदु पर फंस गया हूं।

मैं लेने के लिए कोशिश कर रहा हूँ: g**x जहां

g = 256 bit number 
x = 256 bit number 

अजगर इस बिंदु पर लटका हुआ है, मैं मंचों की बहुत पढ़ा है, धागे etcc लेकिन केवल निष्कर्ष पर आते हैं कि यह के लिए अपने मुश्किल के रूप में अजगर रुक जाता है, ऐसी बड़ी संख्याओं को संसाधित करने के लिए।

कोई विचार यह कैसे किया जा सकता है? कोड के किसी भी दो लाइन टुकड़े, किसी पुस्तकालय, कुछ भी किया जा सकता है।

Answer 1

यह लटक नहीं रहा है, यह सिर्फ प्रसंस्करण है। यह अंत में आपको उत्तर देगा, बशर्ते यह पहले स्मृति से बाहर न हो।

मैंने क्रिप्टोग्राफी में ऐसी प्रक्रिया के परिणाम के बारे में नहीं सुना है; आमतौर पर यह कहा गया शक्ति का मॉड्यूलस है। यदि यह आपके मामले में समान है तो आप इसके बजाय pow() के 3-तर्क फ़ॉर्म का उपयोग कर सकते हैं।

Answer 2

मुझे पूरा यकीन नहीं है कि आप जो पाइथन से पूछ रहे हैं उसकी तीव्रता की सराहना करते हैं। x पर x पर कुछ बढ़ाना, 256 बिट्स लंबा है, 2 ** 256 गुणाओं के बराबर कर रहा है, या 115792089237316195423570985008687907853269984665640564039457584007913129639936 गुणात्मकता। जैसा कि आप कल्पना कर सकते हैं, इसमें कुछ समय लग सकता है। और अंतरिक्ष, जो मैं गारंटी देता हूं आपके पास पर्याप्त नहीं है।

Answer 3

आपको x^y की गणना करने की कोशिश नहीं करनी चाहिए, जैसा कि पहले से ही बताया गया है, यह बहुत मुश्किल है (बहुत सारी जगह और प्रसंस्करण शक्ति लेती है)। आपको एल्गोरिदम को देखने की आवश्यकता है जो आपके लिए कम गुणात्मक संचालन के साथ समस्या का समाधान करे। स्टार्टर्स के लिए http://en.wikipedia.org/wiki/Exponentiation_by_squaring पर एक नज़र डालें।

मॉड्यूलर एक्सपोनेंटिएशन भी बहुत अच्छी तरह से समझा जाता है: http://en.wikipedia.org/wiki/Modular_exponentiation।

आपको http://gmpy.sourceforge.net/ जैसी बड़ी संख्याओं के लिए एक पायथन लाइब्रेरी का उपयोग करने की आवश्यकता होगी।

यदि यह कोई मदद है, तो मैंने mpir का उपयोग कर सी में मॉड्यूलर एक्सपोनेंटिएशन किया था। मैं उस कोड को संलग्न करूंगा, आपको इसे निश्चित रूप से पायथन में परिवर्तित करने की आवश्यकता होगी।

int power_modn(mpz_t c, mpz_t b, mpz_t e, mpz_t n) 
{ 
     mpz_t result; 
     mpz_t one; 
     mpz_t r; 

     mpz_t modulus; mpz_t exponent; mpz_t base; 

     mpz_init(modulus); mpz_init(exponent); mpz_init(base); 
     mpz_init(result); mpz_init(one); mpz_init(r); 

     mpz_set_ui(result, 1); 
     mpz_set_ui(one, 1); 

     mpz_set(base, b); 
     mpz_set(exponent, e); 
     mpz_set(modulus, n); 

     while (mpz_cmp_ui(exponent, 0) > 0) 
     { 
       if (mpz_mod_ui(r, exponent, 2) == 1) 
       { 
         mpz_mul(result, result, base); 
         mpz_mod(result, result, modulus); 
       }; 
       mpz_mul(base, base, base); 
       mpz_mod(base, base, modulus); 
       mpz_fdiv_q_ui(exponent, exponent, 2); 
     } 

     mpz_set(c, result); 
    return 0; 
}