Extended Euclidean Algorithm in Cryptography in Hindi: मॉड्यूलर इन्वर्स और GCD की विस्तृत जानकारी

Extended Euclidean Algorithm in Cryptography: विस्तृत यूक्लिडियन एल्गोरिदम

परिचय

Extended Euclidean Algorithm (विस्तारित यूक्लिडियन एल्गोरिदम) गणित की एक महत्वपूर्ण विधि है, जिसका उपयोग Greatest Common Divisor (GCD) खोजने और Modular Inverse प्राप्त करने के लिए किया जाता है। यह एल्गोरिदम क्रिप्टोग्राफी (Cryptography) में बहुत महत्वपूर्ण भूमिका निभाता है, विशेष रूप से **RSA एल्गोरिदम**, **Diffie-Hellman Key Exchange**, और **Elliptic Curve Cryptography (ECC)** में।

1. यूक्लिडियन एल्गोरिदम (Euclidean Algorithm)

सबसे पहले, हमें समझना होगा कि **Euclidean Algorithm** कैसे काम करता है। यह एल्गोरिदम दो पूर्णांकों a और b के बीच GCD निकालने के लिए प्रयुक्त होता है।

**यूक्लिडियन एल्गोरिदम का सूत्र:**

[ GCD(a, b) = GCD(b, a mod b) ]

जब तक b शून्य नहीं हो जाता, हम a को b से विभाजित करके बचा हुआ शेष (remainder) को नए **a** के रूप में उपयोग करते हैं।

उदाहरण:

मान लीजिए हमें **GCD(30, 12)** निकालना है:

• ( 30 div 12 = 2 ) शेष ( 6 ) ⇒ ( GCD(30, 12) = GCD(12, 6) )
• ( 12 div 6 = 2 ) शेष ( 0 ) ⇒ ( GCD(12, 6) = 6 )

इसलिए, **GCD(30, 12) = 6** होगा।

2. एक्सटेंडेड यूक्लिडियन एल्गोरिदम (Extended Euclidean Algorithm)

Extended Euclidean Algorithm केवल **GCD** नहीं निकालता, बल्कि यह ऐसे **x** और **y** मान भी खोजता है जिससे:

[ a imes x + b imes y = GCD(a, b) ]

इस समीकरण को **Bezout’s Identity** भी कहा जाता है।

2.1 एक्सटेंडेड यूक्लिडियन एल्गोरिदम के चरण

1. सामान्य यूक्लिडियन एल्गोरिदम का उपयोग करके **GCD(a, b)** खोजें।
2. पिछले चरण में मिले विभाजनों का उपयोग करके **x** और **y** मान निकालें।
3. इन मानों का उपयोग **Modular Inverse** खोजने के लिए करें।

2.2 उदाहरण: Extended Euclidean Algorithm

मान लीजिए हमें ( 30 ) और ( 12 ) के लिए **x** और **y** निकालने हैं:

[ 30 = 12 imes 2 + 6 ]

[ 12 = 6 imes 2 + 0 ]

चूंकि GCD = 6 है, हमें ऐसे **x** और **y** खोजने होंगे जिससे:

[ 30 imes x + 12 imes y = 6 ]

हम बैक-सब्स्टिट्यूशन से हल कर सकते हैं:

• ( 6 = 30 - 12 imes 2 )
• ( Rightarrow 6 = 30 imes 1 + 12 imes (-2) )

तो **x = 1 और y = -2** है।

3. क्रिप्टोग्राफी में एक्सटेंडेड यूक्लिडियन एल्गोरिदम का उपयोग

3.1 मॉड्यूलर इन्वर्स (Modular Inverse)

यदि हमें किसी संख्या **a** का मॉड्यूलर इन्वर्स **m** के लिए चाहिए, तो हमें एक **x** खोजना होगा जिससे:

[ a imes x equiv 1 mod m ]

इसका हल Extended Euclidean Algorithm का उपयोग करके निकाला जा सकता है।

उदाहरण: 3 का मॉड्यूलर इन्वर्स 26 के लिए खोजें

हमें **x** ढूंढना है जिससे:

[ 3 imes x equiv 1 mod 26 ]

हम Extended Euclidean Algorithm से हल करेंगे:

• ( 26 = 3 imes 8 + 2 )
• ( 3 = 2 imes 1 + 1 )
• ( 2 = 1 imes 2 + 0 ) (यहाँ GCD = 1, इसलिए इन्वर्स मौजूद है)

अब, बैक-सब्स्टिट्यूशन से:

• ( 1 = 3 - 2 imes 1 )
• ( 2 = 26 - 3 imes 8 )
• ( 1 = 3 - (26 - 3 imes 8) imes 1 )
• ( 1 = 3 imes 9 - 26 imes 1 )

तो **x = 9** है। इसलिए, **3 का 26 के प्रति मॉड्यूलर इन्वर्स 9 होगा**।

निष्कर्ष

Extended Euclidean Algorithm **GCD**, **Modular Inverse**, और **Bezout’s Identity** को खोजने के लिए अत्यंत महत्वपूर्ण है। यह RSA, Diffie-Hellman, और अन्य क्रिप्टोग्राफिक एल्गोरिदम में प्रयुक्त होता है।