मॉड्यूलर घातांक जावा

Question

में मैं कोई तरीका होना चाहिए गणना करने के लिए:

(g^u * y^v) mod p 

जावा में

।

मैं की गणना के लिए इस एल्गोरिथ्म पाया है (छ^यू) आधुनिक p:

int modulo(int a,int b,int c) { 
    long x=1 
    long y=a; 
    while(b > 0){ 
     if(b%2 == 1){ 
      x=(x*y)%c; 
     } 
     y = (y*y)%c; // squaring the base 
     b /= 2; 
    } 
    return (int) x%c; 
} 

और यह बहुत अच्छा काम करता है, लेकिन मैं

(g^u * y^v) mod p 

के लिए ऐसा करने के लिए एक रास्ता खोजने के लिए नहीं कर पा रहे

क्योंकि मेरे गणित कौशल कमजोर हैं।

इसे संदर्भ में रखने के लिए, यह "कम" डीएसए के जावा कार्यान्वयन के लिए है - सत्यापन करने वाले भाग को हल करने की आवश्यकता है।

Answer 1

यह मानते हुए कि दो कारकों नहीं अतिप्रवाह, मैं तुम्हें विश्वास करेंगे इस तरह की अभिव्यक्ति को इस तरह से सरल बना सकते हैं:

(x * y) mod p = ((x mod p)*(y mod p)) mod p। मुझे यकीन है कि आप इसे वहां से समझ सकते हैं।

Answer 2

प्रयास करें

(Math.pow (क्यू, यू) * Math.pow (y, v))% p

Answer 3

कोड का टुकड़ा लागू करता है यही कारण है कि अच्छी तरह से जाना "तेजी से घातांक" एल्गोरिथ्म, भी Exponentiation by squaring के रूप में जाना।

यह इस तथ्य का भी उपयोग करता है कि (ए * बी) मॉड पी = ((एक मॉड पी) * (बी मोड पी)) मॉड पी। (दोनों अतिरिक्त और गुणात्मक प्राइम मॉड्यूलस लेने के तहत संरचित संरचनाएं हैं - यह एक होमोमोर्फिज्म है)। इस तरह एल्गोरिदम में हर बिंदु पर यह पी से छोटे संख्याओं को कम कर देता है।

जबकि आप इन्हें लूप में एक अंतःस्थापित फैशन में गणना करने का प्रयास कर सकते हैं, ऐसा करने के लिए कोई वास्तविक लाभ नहीं है। बस उन्हें अलग से गणना करें, उन्हें एक साथ गुणा करें, और आखिरी बार मोड लें।

चेतावनी दीजिये कि यदि आप पी^2 सबसे बड़ा प्रतिनिधित्व करने योग्य int से अधिक है तो आपको अतिप्रवाह मिलेगा, और इससे आपको गलत जवाब मिल जाएगा। जावा के लिए, बड़े पूर्णांक पर स्विच करना समझदार हो सकता है, या कम से कम पी के आकार पर रनटाइम जांच कर रहा है और अपवाद फेंक सकता है।

अंत में, यदि यह क्रिप्टोग्राफिक उद्देश्यों के लिए है, तो आपको शायद इसे स्वयं लागू करने के बजाय ऐसा करने के लिए लाइब्रेरी का उपयोग करना चाहिए। काम में प्रतीत होता है कि कुछ गलत गलत करना बहुत आसान है, लेकिन कोई सुरक्षा के लिए न्यूनतम प्रदान करता है।