💻 computer science

Double Index Calculus Algorithm: Faster Solving Discrete Logarithm Problem in Finite Prime Field

यह शोध पत्र डबल इंडेक्स कैलकुलस एल्गोरिदम (Double Index Calculus Algorithm) प्रस्तुत करता है, जो परिमित अभाज्य क्षेत्रों (finite prime fields) में डिस्क्रीट लॉगरिदम समस्या को हल करने के लिए एक नवीन विधि है, जो अत्याधुनिक इंडेक्स कैलकुलस एल्गोरिदम की तुलना में महत्वपूर्ण गति सुधार प्रदान करती है और तब भी कार्यक्षमता बनाए रखती है जब आधार (base) एक गुणात्मक जनरेटर (multiplicative generator) नहीं होता है।

मूल लेखक: Wen Huang

प्रकाशित 2026-05-27

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Wen Huang

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

यहाँ "डबल इंडेक्स कैलकुलस एल्गोरिदम" (Double Index Calculus Algorithm) के पेपर का सरल भाषा और रोज़मर्रा के उदाहरणों के साथ विवरण दिया गया है।

बड़ी समस्या: "डिजिटल लॉक"

कल्पना कीजिए कि एक विशाल डिजिटल तिजोरी (एक क्रिप्टोग्राफिक सिस्टम) है जो आपके बैंक खाते या गुप्त संदेशों की रक्षा करती है। इस तिजोरी की सुरक्षा एक विशेष गणितीय पहेली पर टिकी है जिसे डिस्क्रीट लॉगरिदम प्रॉब्लम (Discrete Logarithm Problem) कहा जाता है।

इसे एक विशाल कॉम्बिनेशन लॉक की तरह समझें। आपके पास एक शुरुआती संख्या (जिसे "जेनेरेटर" कहते हैं) है और आप अंतिम परिणाम प्राप्त करने के लिए इसे बार-बार खुद से गुणा करते हैं।

आसान तरीका: यदि मैं आपको शुरुआती संख्या बता दूँ और यह भी बता दूँ कि इसे कितनी बार गुणा किया गया है, तो आप आसानी से अंतिम परिणाम निकाल सकते हैं।
कठिन तरीका: यदि मैं आपको केवल शुरुआती संख्या और अंतिम परिणाम दे दूँ, तो यह पता लगाना कि इसे कितनी बार गुणा किया गया था, अविश्वसनीय रूप से कठिन है। यही कठिनाई आपके डेटा को सुरक्षित रखती है।

दशकों तक, इस ताले को तोड़ने (समस्या को हल करने) का सबसे तेज़ तरीका इंडेक्स कैलकुलस एल्गोरिदम (Index Calculus Algorithm) नामक एक पुराना तरीका था। यह एक मास्टर की-रिंग रखने जैसा है जिसमें आपको अपनी ज़रूरत वाले विशिष्ट दरवाज़े को खोलने के लिए एक विशाल इमारत के हर एक ताले की चाबियाँ ढूँढनी पड़ती हैं।

नया समाधान: "डबल इंडेक्स कैलकुलस"

इस पेपर के लेखक डबल इंडेक्स कैलकुलस एल्गोरिदम नामक एक नई विधि प्रस्तावित करते हैं। उनका दावा है कि यह नई विधि पुराने तरीके की तुलना में काफी तेज़ है—विशेष रूप से जब संख्याएँ बहुत बड़ी हो जाती हैं, तो यह कभी-कभी 30 गुना से भी अधिक तेज़ होती है।

वे इसे कैसे करते हैं, यहाँ एक सरल उदाहरण दिया गया है:

1. पुराना तरीका: "सब-कुछ-या-कुछ-भी-नहीं" वाली की-रिंग

कल्पना कीजिए कि आपको एक विशिष्ट दरवाज़ा खोलना है (गुप्त संख्या ढूँढनी है)। पुराना तरीका कहता है:

"इस दरवाज़े को खोलने के लिए, आपको पहले इमारत के हर एक कमरे (फैक्टर बेस) की चाबियाँ ढूँढ़नी होंगी।"
आपको कमरे दर कमरे जाना होगा, कमरा 1 की चाबी ढूँढनी होगी, फिर कमरा 2, और इसी तरह कमरा 1,000 तक जाना होगा।
जब आपके पास सभी 1,000 चाबियाँ आ जाएँगी, तभी आप अंततः अपने विशिष्ट दरवाज़े को खोलने का तरीका जान पाएंगे।
खामी: यदि आप एक भी चाबी भूल जाते हैं, या यदि किसी विशिष्ट कमरे के लिए चाबी मौजूद नहीं है, तो पूरी प्रक्रिया विफल हो जाती है।

2. नया तरीका: "दो-ट्रैक" दौड़

नया तरीका नियमों को बदल देता है। सभी चाबियाँ ढूँढने के बजाय, यह दो अलग-अलग दृष्टिकोणों (या "बेसिस") के उपयोग वाला एक चतुर तरीका अपनाता है।

कल्पना कीजिए कि आप भीड़ में किसी विशिष्ट व्यक्ति को ढूँढ रहे हैं।

पुराना तरीका: आपको उस व्यक्ति को खोजने के लिए भीड़ में मौजूद हर एक व्यक्ति का इंटरव्यू लेना होगा।
नया तरीका: आप जासूसों की दो टीमें भेजते हैं।
- टीम A "लाल चश्मे" का उपयोग करके उस व्यक्ति को ढूँढती है।
- टीम B "नीले चश्मे" का उपयोग करके उस व्यक्ति को ढूँढती है।

जादू यह है कि आपको सबको ढूँढने की ज़रूरत नहीं है। आपको केवल एक ऐसा व्यक्ति ढूँढना है जिसे टीम A और टीम B दोनों ने देखा हो।

जैसे ही टीम A को एक व्यक्ति मिलता है (मान लीजिए "प्राइम नंबर 7") और टीम B भी "प्राइम नंबर 7" को ढूँढ लेती है, दौड़ समाप्त हो जाती है।
आपको अन्य 999 कमरों की चाबियाँ ढूँढने की ज़रूरत नहीं है। आपको बस वह एक ओवरलैप (मिलान) चाहिए।
क्योंकि आप एक साथ दो खोज (सर्च) चला रहे हैं, इसलिए उस एक ओवरलैप को जल्दी खोजने की संभावना बहुत अधिक होती है, बिना हर एक कमरे की जाँच किए।

यह एक बड़ी बात क्यों है?

1. यह बहुत तेज़ है
पेपर में कंप्यूटर पर प्रयोग किए गए। जब संख्याएँ 70 बिट्स लंबी थीं (जो कुछ सुरक्षा प्रणालियों के लिए एक मानक आकार है), तो नया एल्गोरिदम पुराने वाले की तुलना में 34 गुना तेज़ था।

उदाहरण: यदि पुराने तरीके को पहेली सुलझाने में 34 घंटे लगते, तो नया तरीका इसे केवल 1 घंटे में कर देता।

2. यह तब भी काम करता है जब पुराना तरीका विफल हो जाता है
कभी-कभी, "लॉक" अजीब तरीके से टूटा होता है (शुरुआती संख्या एक आदर्श "जेनेरेटर" नहीं होती)।

पुराना तरीका: यदि लॉक अजीब है, तो कुछ चाबियाँ मौजूद नहीं हो सकती हैं। पुराना तरीका अटक जाता है और हार मान लेता है।
नया तरीका: क्योंकि इसे केवल एक ऐसे मिलान वाली चाबी की आवश्यकता होती है जिसे दोनों टीमों ने पाया हो, इसलिए यह अक्सर पहेली को हल कर सकता है भले ही लॉक अजीब हो या कुछ चाबियाँ गायब हों। यह अधिक लचीला है।

3. यह एक "डबल" प्रयास है
"डबल इंडेक्स कैलकुलस" नाम इस तथ्य से आता है कि एल्गोरिदम जानकारी की दो अलग-अलग सूचियाँ बनाता है (एक मूल संख्या पर आधारित, दूसरी लक्ष्य संख्या पर आधारित) और उनके मिलान (इंटरसेक्शन) को देखता है। यह एक ही क्षेत्र के दो अलग-अलग मानचित्रों के होने जैसा है; आपको दोनों मानचित्रों पर पूरे क्षेत्र की खोज करने की आवश्यकता नहीं है, आपको बस यह ढूँढना है कि दोनों मानचित्र कहाँ मिलते हैं।

सारांश

लेखकों ने "डिस्क्रीट लॉगरिदम" की गणितीय पहेली को हल करने का एक स्मार्ट तरीका ईजाद किया है। पहेली के हर एक हिस्से को ढूँढने की कड़ी मेहनत करने (पुराने तरीके की तरह) के बजाय, उनका नया तरीका एक साथ दो खोज चलाता है और जैसे ही दोनों खोज आपस में मिलती हैं, रुक जाता है।

परिणाम: उनका दावा है कि यह इन विशिष्ट डिजिटल तालों को तोड़ने की प्रक्रिया को वर्तमान सर्वश्रेष्ठ तकनीक की तुलना में 30+ गुना तेज़ बना देता है।

महत्वपूर्ण नोट: यह पेपर पूरी तरह से इस विशिष्ट समस्या को हल करने की गणितीय गति पर केंद्रित है। यह दावा नहीं करता है कि यह तुरंत वास्तविक दुनिया के बैंक खातों या सरकारी रहस्यों को तोड़ देगा, न ही यह नैदानिक (clinical) या चिकित्सा अनुप्रयोगों के बारे में चर्चा करता है। यह क्रिप्टोग्राफी गणित के क्षेत्र में एक सैद्धांतिक और प्रयोगात्मक सफलता है।

तकनीकी सारांश: डिस्क्रीट लॉगरिदम समस्याओं के लिए डबल इंडेक्स कैलकुलस एल्गोरिदम

समस्या विवरण
यह शोध पत्र परिमित अभाज्य क्षेत्रों (finite prime fields) में डिस्क्रीट लॉगरिदम प्रॉब्लम (DLP) को संबोधित करता है, जो सार्वजनिक-कुंजी एन्क्रिप्शन और डिजिटल हस्ताक्षर सहित कई क्रिप्टोग्राफिक योजनाओं की सुरक्षा का आधार है। जबकि इंडेक्स कैलकुलस एल्गोरिदम और इसके वेरिएंट (जैसे कि नंबर फील्ड सीव और फंक्शन फील्ड सीव) इन क्षेत्रों में DLP को हल करने के लिए अत्याधुनिक (state-of-the-art) समाधान हैं, वे विशिष्ट सीमाओं का सामना करते हैं। मुख्य रूप से, इन एल्गोरिदमों को फैक्टर बेस (आकार $k$ ) के सभी अभाज्य संख्याओं के डिस्क्रीट लॉगरिदम और लक्षित पूर्णांक (target integer) की गणना करने की आवश्यकता होती है, जिससे कुल $k+1$ लॉगरिदम की आवश्यकता होती है, इससे पहले कि लक्ष्य को हल किया जा सके। इसके अलावा, मानक इंडेक्स कैलकुलस एल्गोरिदम अक्सर विफल हो जाते हैं यदि DLP का आधार (base) क्षेत्र का मल्टीप्लिकेशन जनरेटर नहीं है, क्योंकि फैक्टर बेस के कुछ अभाज्य संख्याओं के डिस्क्रीट लॉगरिदम मौजूद नहीं हो सकते हैं।

कार्यप्रणाली: डबल इंडेक्स कैलकुलस एल्गोरिदम
लेखक "डबल इंडेक्स कैलकुलस एल्गोरिदम" प्रस्तावित करते हैं, जो आवश्यक डिस्क्रीट लॉगरिदम की संख्या को कम करके DLP को हल करने के दृष्टिकोण को मौलिक रूप से बदल देता है।

दोहरी समीकरण प्रणालियाँ (Dual Equation Systems): एक एकल लक्षित समीकरण को निर्धारित करने के बजाय, एल्गोरिदम दो अलग-अलग रैखिक समीकरण प्रणालियों का निर्माण करता है:
- एक प्रणाली जनरेटर $g$ के सापेक्ष फैक्टर बेस के अभाज्य संख्याओं के डिस्क्रीट लॉगरिदम की गणना करती है (अर्थात $\log_g p_i$ ज्ञात करना)।
- दूसरी प्रणाली उसी फैक्टर बेस की अभाज्य संख्याओं के लक्षित आधार $b$ के सापेक्ष डिस्क्रीट लॉगरिदम की गणना करती है (अर्थात $\log_b p_i$ ज्ञात करना)।
इंटरसेक्शन रणनीति (Intersection Strategy): मुख्य नवाचार एक ऐसे अभाज्य $p_i$ की पहचान करना है जिसके लिए फैक्टर बेस में $\log_g p_i$ और $\log_b p_i$ दोनों को सफलतापूर्वक परिकलित किया गया है।
लक्ष्य समाधान (Target Solution): एक बार जब ऐसा एक अभाज्य मिल जाता है, तो एल्गोरिदम संबंध का उपयोग करके लक्षित डिस्क्रीट लॉगरिदम $x$ (जहाँ $g^x \equiv b \pmod p$ ) को हल करता है:
$x \equiv \alpha \beta^{-1} \pmod{p-1}$
जहाँ $g^\alpha \equiv p_i \pmod p$ और $b^\beta \equiv p_i \pmod p$ है।
संभाव्यता दक्षता (Probabilistic Efficiency): एल्गोरिदम स्मूथ इंटीजर्स (smooth integers) खोजने की संभाव्य प्रकृति पर निर्भर करता है। जबकि मानक इंडेक्स कैलकुलस एल्गोरिदम को नियत रूप से (deterministically) $k+1$ लॉगरिदम हल करने होते हैं, डबल इंडेक्स कैलकुलस एल्गोरिदम तब सफल हो सकता है जब दो कंप्यूट किए गए लॉगरिदम के सेट का इंटरसेक्शन (intersection) गैर-रिक्त (non-empty) हो। लेखक तर्क देते हैं कि "नाइस केसेस" (वे परिदृश्य जहाँ लक्ष्य $k+1$ से कम लॉगरिदम के साथ हल करने योग्य होता है) की संख्या बहुत अधिक है, जिससे शीघ्र समाप्ति (early termination) की उच्च संभावना मिलती है।
समानांतर प्रसंस्करण (Parallelization): आधार $g$ और आधार $b$ के लॉगरिदम की गणना स्वतंत्र प्रक्रियाएं हैं, जो समानांतर निष्पादन (parallel execution) की अनुमति देती हैं, जिससे कुल रनिंग टाइम दो समानांतर प्रक्रियाओं के योग के बजाय उनके अधिकतम (maximum) में बदल जाता है।

प्रमुख योगदान

सैद्धांतिक सफलता: यह शोध पत्र आवश्यक डिस्क्रीट लॉगरिदम की संख्या में सैद्धांतिक कमी का दावा करता है। जबकि पारंपरिक तरीकों के लिए $k+1$ लॉगरिदम की आवश्यकता होती है, प्रस्तावित एल्गोरिदम दो आंशिक लॉगरिदम सेटों के इंटरसेक्शन का लाभ उठाकर $k+1$ से कम लॉगरिदम के साथ समस्या को हल कर सकता है।
उन्नत व्यापकता (Enhanced Generality): एल्गोरिदम को तब भी काम करने के लिए डिज़ाइन किया गया है जब आधार $g$ क्षेत्र का मल्टीप्लिकेशन जनरेटर नहीं होता है। ऐसे मामलों में, जहाँ मानक इंडेक्स कैलकुलस विफल हो सकता है क्योंकि कुछ अभाज्य संख्याओं के लिए $\log_g p_i$ मौजूद नहीं होता है, डबल इंडेक्स कैलकुलस तब भी सफल हो सकता है जब तक कि कम से कम एक ऐसा अभाज्य मौजूद हो जिसके लिए $\log_g p_i$ और $\log_b p_i$ दोनों मौजूद हों।
अनुकूलता: यह विधि स्मूथ इंटीजर्स को तेजी से खोजने के लिए उपयोग की जाने वाली मौजूदा अनुकूलन तकनीकों (जैसे सीव विधियों) के साथ संगत है। यह स्मूथ इंटीजर्स को तेजी से खोजने के लिए इन युक्तियों का उपयोग कर सकता है, और फिर अपने स्वयं के तर्क को लागू करके आवश्यक स्मूथ इंटीजर्स की संख्या को कम कर सकता है।

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

स्पीडअप (Speedup): 70 बिट लंबाई वाले परिमित अभाज्य क्षेत्रों के लिए, डबल इंडेक्स कैलकुलस एल्गोरिदम ने इंडेक्स कैलकुलस एल्गोरिदम की तुलना में लगभग 34 गुना की गति वृद्धि प्रदर्शित की (2211 सेकंड बनाम 75426 सेकंड)।
स्केलेबिलिटी (Scalability): जैसे-जैसे बिट लंबाई बढ़ती है, प्रदर्शन का अंतर और अधिक बढ़ जाता है। 50 बिट्स पर, प्रस्तावित एल्गोरिदम लगभग 10 गुना तेज़ था; 70 बिट्स पर, यह 30 गुना से अधिक तेज़ था।
स्मूथनेस बाउंड (Smoothness Bound): प्रयोगों से संकेत मिला कि प्रस्तावित एल्गोरिदम के लिए इष्टतम स्मूथनेस बाउंड मानक इंडेक्स कैलकुलस से थोड़ा भिन्न होता है (अक्सर $0.5B_i$ के मुकाबले लगभग $0.65B_i$ ), लेकिन प्रस्तावित एल्गोरिदम विभिन्न बिट लंबाई (30 से 75 बिट्स) में लगातार कम औसत रनिंग टाइम बनाए रखता है।

महत्व और दावे
यह शोध पत्र डबल इंडेक्स कैलकुलस एल्गोरिदम को परिमित अभाज्य क्षेत्रों में DLP को हल करने के लिए वर्तमान अत्याधुनिक (state-of-the-art) समाधानों से एक महत्वपूर्ण सुधार के रूप में प्रस्तुत करता है। लेखक दावा करते हैं कि आवश्यक डिस्क्रीट लॉगरिदम की संख्या को कम करके, उनका एल्गोरिदम कंप्यूटिंग गति में पर्याप्त वृद्धि प्राप्त करता है। वे तर्क देते हैं कि यह सुधार केवल मौजूदा सीव विधियों का एक रूपांतर नहीं है, बल्कि समाधान प्रक्रिया में एक संरचनात्मक परिवर्तन है। लेखकों का सुझाव है कि ये परिणाम इस बात को प्रभावित कर सकते हैं कि शोधकर्ता DLP की कठोरता (hardness) पर निर्भर क्रिप्टोग्राफिक योजनाओं के लिए सुरक्षा पैरामीटर कैसे चुनते हैं, क्योंकि मानक इंडेक्स कैलकुलस जटिलता मॉडल द्वारा अनुमानित प्रभावी सुरक्षा स्तर से दिया गया की-साइज़ (key size) कम हो सकता है।