Index calculus algorithm
कम्प्यूटेशनल संख्या सिद्धांत में, सूचकांक कलन एल्गोरिथ्म असतत लघुगणक की गणना के लिए एक संभावित एल्गोरिथ्म है। जहाँ एक अभाज्य है, वहाँ असतत लघुगणक को समर्पित, सूचकांक कलन परिमित क्षेत्रों और दीर्घवृत्ताकार वक्रों के कुछ परिवारों के लिए अनुकूलित एल्गोरिदम के एक परिवार की ओर ले जाता है। एल्गोरिथ्म छोटे अभाज्य संख्याओं के असतत लघुगणक के बीच संबंधों को एकत्र करता है, एक रैखिक बीजगणित प्रक्रिया द्वारा उनकी गणना करता है और अंत में छोटे अभाज्य संख्याओं के असतत लघुगणक के संबंध में वांछित असतत लघुगणक को व्यक्त करता है। विवरण मोटे तौर पर, असतत लॉग समस्या हमें एक x खोजने के लिए कहती है, जहाँ g, h और मापांक n दिए गए हैं। एल्गोरिथ्म (नीचे विस्तार से वर्णित) उस समूह पर लागू होता है जहाँ q अभाज्य है। इसके लिए इनपुट के रूप में एक कारक आधार की आवश्यकता होती है। इस कारक आधार को आमतौर पर संख्या-1 के रूप में चुना जाता है और पहला r अभाज्य 2 से शुरू होता है। दक्षता के दृष्टिकोण से, हम चाहते हैं कि यह कारक आधार छोटा हो, लेकिन एक बड़े समूह के लिए असतत लॉग को हल करने के लिए हमें कारक आधार (अपेक्षाकृत) बड़ा होना चाहिए। एल्गोरिदम के व्यावहारिक कार्यान्वयन में, उन परस्पर विरोधी उद्देश्यों से किसी न किसी तरह से समझौता किया जाता है। एल्गोरिथ्म तीन चरणों में किया जाता है। पहले दो चरण केवल जनरेटर g और अभाज्य मापांक q पर निर्भर करते हैं, और r छोटे अभाज्य संख्याओं के कारक आधार के असतत लघुगणक का पता लगाते हैं। तीसरा चरण कारक आधार के असतत लॉग के संदर्भ में वांछित संख्या एच का असतत लॉग पाता है। पहले चरण में कारक आधार और जनरेटर की शक्ति के बीच r रैखिक रूप से स्वतंत्र संबंधों के एक समूह की खोज होती है। प्रत्येक संबंध r अज्ञात में रैखिक समीकरणों की एक प्रणाली में एक समीकरण का योगदान देता है, अर्थात् कारक आधार में r अभाज्य संख्याओं के असतत लघुगणक। यह चरण शर्मनाक रूप से समानांतर है और कई कंप्यूटरों के बीच विभाजित करना आसान है। दूसरा चरण कारक आधार के असतत लॉग की गणना करने के लिए रैखिक समीकरणों की प्रणाली को हल करता है। सैकड़ों हजारों या लाखों समीकरणों की एक प्रणाली एक महत्वपूर्ण गणना है जिसमें बड़ी मात्रा में स्मृति की आवश्यकता होती है, और यह शर्मनाक रूप से समानांतर नहीं है, इसलिए आमतौर पर एक सुपर कंप्यूटर का उपयोग किया जाता है। इसे छोटे असतत लॉग गणनाओं के लिए दूसरों की तुलना में एक छोटा कदम माना जाता था। हालांकि, बड़े असतत लघुगणक रिकॉर्ड केवल कार्य को रैखिक बीजगणित से दूर और छलनी पर स्थानांतरित करके संभव बनाए गए थे (यानी, चरों की संख्या को कम करते हुए समीकरणों की संख्या में वृद्धि)। तीसरा चरण जनरेटर g की एक शक्ति s की खोज करता है, जिसे जब तर्क h से गुणा किया जाता है, तो कारक आधार gsh = (−1) f0 2f1 3f2··prfr के संदर्भ में फैक्टर किया जा सकता है। अंत में, एक ऐसे ऑपरेशन में जिसे वास्तव में चौथा चरण नहीं कहा जा सकता है, दूसरे और तीसरे चरण के परिणामों को सरल बीजगणितीय हेरफेर द्वारा वांछित असतत लघुगणक x = f0log (−1) + f1log2 + f2log3 + ·· + frlogpr − s पर काम करने के लिए पुनर्व्यवस्थित किया जा सकता है। पहले और तीसरे चरण दोनों शर्मनाक रूप से समानांतर हैं, और वास्तव में तीसरा चरण पहले दो चरणों के परिणामों पर निर्भर नहीं करता है, इसलिए इसे उनके समानांतर किया जा सकता है। कारक आधार आकार r का चयन महत्वपूर्ण है, और विवरण यहाँ समझाने के लिए बहुत जटिल हैं। कारक आधार जितना बड़ा होगा, चरण 1 में संबंधों को खोजना उतना ही आसान होगा, और चरण 3 को पूरा करना उतना ही आसान होगा, लेकिन चरण 2 पर आगे बढ़ने से पहले आपको जितने अधिक संबंधों की आवश्यकता होगी, और चरण 2 उतना ही कठिन होगा। चरण 1 और 2 के लिए आवश्यक विभिन्न प्रकार की गणना के लिए उपयुक्त कंप्यूटरों की सापेक्ष उपलब्धता भी महत्वपूर्ण है। अन्य समूहों में अनुप्रयोग अण्डाकार वक्रों पर बिंदुओं के समूह में प्रमुख तत्वों की धारणा की कमी से सूचकांक कलन विधि को चलाने के लिए एक कुशल कारक आधार खोजना असंभव हो जाता है जैसा कि इन समूहों में यहां प्रस्तुत किया गया है। इसलिए यह एल्गोरिथ्म अण्डाकार वक्र समूहों में असतत लघुगणक को कुशलता से हल करने में असमर्थ है। हालांकिः विशेष प्रकार के वक्रों (तथाकथित सुपरसिंगुलर एलिप्टिक वक्र) के लिए सामान्य विधियों की तुलना में समस्या को तेजी से हल करने के लिए विशेष एल्गोरिदम हैं। हालांकि इन विशेष वक्रों के उपयोग से आसानी से बचा जा सकता है, 2009 में यह साबित हुआ है कि कुछ क्षेत्रों के लिए इन क्षेत्रों पर सामान्य अण्डाकार वक्रों पर बिंदुओं के समूह में असतत लघुगणक समस्या को सामान्य तरीकों की तुलना में तेजी से हल किया जा सकता है। एल्गोरिदम वास्तव में सूचकांक कलन विधि के अनुकूलन हैं। एल्गोरिथ्म इनपुटः असतत लघुगणक जनरेटर, मापांक और तर्क। कारक आधार, लंबाई का। आउटपुटः ऐसा। संबंधों के लिए खाली सूची चिकनी संख्याओं के लिए अनुकूलित एक पूर्णांक गुणनखंडन एल्गोरिथ्म का उपयोग करते हुए, कारक आधार का उपयोग करके कारक (यूक्लिडियन अवशेष) बनाने का प्रयास करें, अर्थात। यदि कम से कम संबंध हैं, तो एक मैट्रिक्स बनाएँ जिसकी पंक्तियाँ संबंध हैं मैट्रिक्स का कम ईचेलॉन रूप प्राप्त करें अंतिम कॉलम में पहला तत्व असतत लॉग ऑफ है और दूसरा तत्व असतत लॉग ऑफ है और इसी तरह के लिए कारक आधार पर कारक बनाने की कोशिश करें जब एक फैक्टराइजेशन पाया जाता हैः आउटपुट जटिलता कारक आधार का एक इष्टतम चयन मानते हुए, सूचकांक-कैलकुलस एल्गोरिथ्म का अपेक्षित चलने का समय (एल-नोटेशन का उपयोग करके) के रूप में बताया जा सकता है। एल्गोरिथम का मूल विचार पश्चिमी और मिलर (1968) के कारण है, जो अंततः क्रैचिक (1922) के विचारों पर निर्भर करता है। पहला व्यावहारिक कार्यान्वयन 1976 में डिफी-हेलमैन क्रिप्टोसिस्टम की शुरुआत के बाद हुआ जो असतत लघुगणक पर निर्भर करता है। मर्केल के स्टैनफोर्ड विश्वविद्यालय के शोध प्रबंध (1979) का श्रेय पोहलिग (1977) और हेलमैन और रेनेरी (1983) को दिया गया, जिन्होंने कार्यान्वयन में भी सुधार किए। एडलमैन ने एल्गोरिथ्म को अनुकूलित किया और इसे वर्तमान रूप में प्रस्तुत किया। सूचकांक कैलकुलस परिवार सूचकांक कैलकुलस ने एल्गोरिदम के एक बड़े परिवार को प्रेरित किया। कुछ अभाज्य के साथ परिमित क्षेत्रों में, अत्याधुनिक एल्गोरिदम असतत लघुगणक के लिए संख्या क्षेत्र छलनी हैं, जब कार्य क्षेत्र छलनी की तुलना में बड़ा होता है, और जॉक्स, जब की तुलना में छोटा होता है और उच्च डिग्री में संख्या क्षेत्र छलनी, जब मध्य-पक्षीय होता है। अण्डाकार वक्रों के कुछ परिवारों में असतत लघुगणक को समय पर हल किया जा सकता है, लेकिन सामान्य मामला घातीय रहता है। बाहरी लिंक 21 जून, 2002 के पेपर "द डिस्क्रीट लॉग प्रॉब्लम" सहित क्रिस स्टडहोल्म द्वारा एंड्रयू ओडलीज़्को डिस्क्रीट लॉगरिथम प्रॉब्लम द्वारा सीमित क्षेत्रों में डिस्क्रीट लॉगरिदम और उनके क्रिप्टोग्राफिक महत्व को जोड़ते हैं। नोट्स समूह सिद्धांत