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

परिचय

यूक्लिडियन एल्गोरिद्म (Euclidean Algorithm) संख्या सिद्धांत (Number Theory) का एक अत्यंत प्राचीन और शक्तिशाली एल्गोरिद्म है, जिसका उपयोग दो पूर्णांकों के महत्तम समापवर्तक (Greatest Common Divisor - GCD) को निकालने के लिए किया जाता है। यह एल्गोरिद्म लगभग 2300 वर्ष पुराना है और सबसे पहले यूनानी गणितज्ञ यूक्लिड (Euclid) द्वारा उनकी प्रसिद्ध पुस्तक “Elements” में प्रस्तुत किया गया था।

यूक्लिडियन एल्गोरिद्म गणित और कंप्यूटर विज्ञान दोनों में अत्यधिक महत्वपूर्ण है क्योंकि यह GCD को निकालने का सबसे तेज़, प्रभावी और तार्किक तरीका प्रदान करता है। आज भी यह एल्गोरिद्म क्रिप्टोग्राफी, डेटा साइंस, और मॉड्यूलर अंकगणित (Modular Arithmetic) में उपयोग किया जाता है।

मुख्य विचार

यूक्लिडियन एल्गोरिद्म इस सरल सिद्धांत पर आधारित है:

यदि a और b दो पूर्णांक हैं (a > b), तो GCD(a, b) = GCD(b, a mod b)

इसका अर्थ यह है कि किसी दो संख्याओं का GCD वही रहता है, चाहे बड़ी संख्या को छोटी संख्या से विभाजित करने पर जो शेष बचे, उसके साथ फिर से प्रक्रिया दोहराई जाए।

प्रक्रिया

1. यदि a और b दो धनात्मक पूर्णांक हैं और a > b, तो a को b से भाग दें।
2. शेषफल (Remainder) r प्राप्त करें।
3. अब GCD(a, b) = GCD(b, r)।
4. इस प्रक्रिया को तब तक दोहराएँ जब तक r = 0 न हो जाए।
5. अंतिम गैर-शून्य (non-zero) remainder GCD होगा।

उदाहरण 1

GCD(60, 36) निकालने के लिए:

60 = 36 × 1 + 24  
36 = 24 × 1 + 12  
24 = 12 × 2 + 0  
→ GCD = 12

इस प्रकार, 60 और 36 का महत्तम समापवर्तक 12 है।

उदाहरण 2

GCD(270, 192) निकालें:

270 = 192 × 1 + 78  
192 = 78 × 2 + 36  
78 = 36 × 2 + 6  
36 = 6 × 6 + 0  
→ GCD = 6

एल्गोरिद्म का छद्म-कोड (Pseudocode)

function GCD(a, b):
    while b ≠ 0:
        temp = b
        b = a mod b
        a = temp
    return a

समय जटिलता (Time Complexity)

यूक्लिडियन एल्गोरिद्म की समय जटिलता O(log(min(a, b))) होती है, जो इसे अत्यंत तेज़ बनाती है — बड़े अंकों के लिए भी। यह क्रिप्टोग्राफी जैसे RSA एल्गोरिद्म में बहुत उपयोगी है जहाँ बहुत बड़ी संख्याओं के साथ गणना करनी पड़ती है।

विस्तारित यूक्लिडियन एल्गोरिद्म (Extended Euclidean Algorithm)

विस्तारित संस्करण का उपयोग उन संख्याओं x और y को खोजने के लिए किया जाता है जो इस समीकरण को संतुष्ट करते हैं:

a×x + b×y = GCD(a, b)

यह समीकरण Bézout's Identity कहलाती है और मॉड्यूलर इनवर्स (Modular Inverse) की गणना में बहुत महत्वपूर्ण है। उदाहरण के लिए, क्रिप्टोग्राफी में Modular Multiplicative Inverse निकालने के लिए इसका उपयोग होता है।

डेटा साइंस और कंप्यूटर विज्ञान में उपयोग

• RSA Encryption Algorithm में सहाभाज्य संख्याएँ खोजने के लिए।
• मॉड्यूलर अंकगणित में Modular Inverse निकालने के लिए।
• अल्गोरिद्मिक ऑप्टिमाइजेशन और Recursive Programming के अध्ययन में।
• Data Reduction या Scaling Operations में सामान्य अनुपात निकालने के लिए।

गुणधर्म (Properties)

• GCD(a, b) = GCD(b, a mod b)
• यदि b | a ⇒ GCD(a, b) = b
• GCD(a, b) = GCD(b, a – b)
• यदि GCD(a, b) = 1, तो (a, b) Coprime कहलाते हैं।

निष्कर्ष

यूक्लिडियन एल्गोरिद्म संख्या सिद्धांत की आधारशिला है। यह सरल नियमों पर आधारित होते हुए भी अत्यधिक कुशल (Efficient) और व्यावहारिक है। डेटा साइंस, क्रिप्टोग्राफी, और गणनात्मक गणित में यह एल्गोरिद्म आज भी एक अनिवार्य उपकरण के रूप में प्रयुक्त होता है।