🔢 mathematics

Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings

यह शोध पत्र दो गैर-क्रमविनिमेय (noncommuting) एंडोमॉर्फिज्म और उनके द्वारा जनरेट किए गए रिंग के डिस्क्रिमिनेन्ट के गुणनखंड का उपयोग करके, कानी के लेम्मा (Kani's Lemma), उच्च-आयामी इसोजेनी (higher-dimensional isogenies) और ब्रुअट-टिट्स ट्री (Bruhat-Tits tree) में पथ-खोज का लाभ उठाकर, एक सुपरसिंगुलर एलिप्टिक कर्व के एंडोमॉर्फिज्म रिंग की गणना के लिए एक नियतात्मक बहुपद-समय (deterministic polynomial-time) एल्गोरिदम प्रस्तुत करता है, जो पिछले उप-घातांकीय (subexponential) और संभाव्य (probabilistic) तरीकों में सुधार करता है।

मूल लेखक: Kirsten Eisentraeger, Gabrielle Scullard

प्रकाशित 2026-01-22

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

CC BY 4.0

मूल लेखक: Kirsten Eisentraeger, Gabrielle Scullard

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

कल्पना कीजिए कि आप एक विशाल, जटिल जिग्सॉ पहेली (jigsaw puzzle) को हल करने की कोशिश कर रहे हैं। जिस चित्र को आप पूरा करने की कोशिश कर रहे हैं, वह एक विशेष प्रकार के गणितीय ऑब्जेक्ट, जिसे सुपरसिंगुलर एलिप्टिक कर्व (supersingular elliptic curve) कहा जाता है, का एंडोमोर्फिज्म रिंग (Endomorphism Ring) है।

गणित की इस दुनिया में (विशेष रूप से उस प्रकार की क्रिप्टोग्राफी में जो क्वांटम कंप्यूटरों से बच सकती है), इस पहेली के सटीक आकार को जानना अत्यंत महत्वपूर्ण है। यदि आप पूरी तस्वीर नहीं जानते, तो सिस्टम सुरक्षित है। यदि आप इसे समझ लेते हैं, तो आप कोड को तोड़ सकते हैं।

लंबे समय तक, इस पूरी तस्वीर को खोजना एक ऐसी स्थिति की तरह था जैसे आँखों पर पट्टी बाँधकर घास के ढेर में सुई ढूँढना। आप कुछ टुकड़े (कुछ गणितीय फलन जिन्हें "एंडोमोर्फिज्म" कहा जाता है) पा सकते थे, लेकिन आपको यह नहीं पता था कि वे मिलकर पूर्ण संरचना कैसे बनाते हैं।

यहाँ किर्स्टन आइजनट्रैगर (Kirsten Eisenträger) और गैब्रिएल स्कुलरड (Gabrielle Scullard) ने इस शोध पत्र में क्या किया है, इसे सरल उपमाओं के माध्यम से समझाया गया है:

1. शुरुआती बिंदु: पहेली के कुछ टुकड़े

शोधकर्ता एक "सब-ऑर्डर" (sub-order) से शुरुआत करते हैं। इसे एक छोटे, अधूरे क्लस्टर की तरह समझें जिसमें आप जानते हैं कि बड़े चित्र के कुछ टुकड़े शामिल हैं। आपके पास दो विशिष्ट टुकड़े हैं जो सरल तरीके से एक साथ फिट नहीं होते (वे "कम्यूट" नहीं करते) और आप जानते हैं कि उनका "डिस्क्रिमिनेंट" (एक गणितीय माप कि आपका क्लस्टर कितना अधूरा है) क्या है।

2. मानचित्र: ब्रुहा-टीट्स ट्री (Bruhat-Tits Tree)

खोए हुए टुकड़ों को खोजने के लिए, लेखक ब्रुहा-टीट्स ट्री नामक मानचित्र का उपयोग करते हैं।

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

3. नए उपकरण: कानी का लेम्मा (Kani's Lemma) और उच्च आयाम (Higher Dimensions)

यह मानचित्र कुशलतापूर्वक नेविगेट करने के लिए शोध पत्र दो मुख्य "सुपरपावर्स" पेश करता है:

"जादुई विभाजक" (Division Algorithm):
कल्पना कीजिए कि आपके पास एक जटिल मशीन (एक एंडोमोर्फिज्म) है और आप जानना चाहते हैं कि क्या इसे छोटी, सरल मशीनों में विभाजित किया जा सकता है। लेखक उच्च-आयामी आइसोजेनी (higher-dimensional isogenies) (जो कि आपकी 2D पहेली को अस्थायी रूप से 3D स्थान में उठाने जैसा है) से जुड़ी एक तकनीक का उपयोग करते हैं। इस 3D स्थान में, यह देखना बहुत आसान है कि क्या एक टुकड़े को साफ तौर पर विभाजित किया जा सकता है। यदि ऐसा है, तो आप जानते हैं कि आप सही रास्ते पर हैं। यह कानी के लेम्मा (Kani's Lemma) पर आधारित है, जो समस्याओं को विभिन्न आयामों के बीच ले जाने की अनुमति देने वाला एक गणितीय नियम है।
"इंटरसेक्शन डिटेक्टर" (Intersection Detector - तु का प्रमेय):
कल्पना कीजिए कि आप एक इमारत में एक विशिष्ट कमरे की तलाश कर रहे हैं। हर कमरे की जाँच करने के बजाय, आप तीन अलग-अलग गलियारों के मिलन बिंदु (intersection) की जाँच करते हैं। यदि एक कमरा मौजूद है जहाँ तीनों गलियारे मिलते हैं, तो आप जानते हैं कि आपको कहाँ देखना है। लेखक तु के प्रमेय (Tu's Theorem) का उपयोग यह दिखाने के लिए करते हैं कि वे कुछ विशिष्ट इंटरसेक्शन की जाँच करके मानचित्र (ट्री) के विशाल हिस्सों को तुरंत खारिज कर सकते हैं। यह उन्हें हजारों गलत रास्तों को तुरंत हटाने की अनुमति देता है।

4. रणनीति: स्थानीय बनाम वैश्विक (Local vs. Global)

एल्गोरिदम पहले समस्या को स्थानीय (locally) रूप से हल करता है, फिर उसे एक साथ जोड़ता है।

स्थानीय (Local): वे विशिष्ट अभाज्य संख्याओं (prime numbers) पर एक "सूक्ष्मदर्शी" के माध्यम से पहेली को देखते हैं (जैसे किसी विशेष रंग की रोशनी के नीचे पहेली को देखना)। प्रत्येक अभाज्य संख्या पर, वे यह पता लगाते हैं कि वे मानचित्र पर पूर्ण समाधान से कितनी दूर हैं।
पथ (The Path): वे केवल अनुमान नहीं लगाते। वे ट्री के नीचे कदम-दर-कदम चलने के लिए एक बाइनरी सर्च (जैसे 1 से 100 के बीच संख्या का अनुमान लगाना कि "क्या यह अधिक है या कम?") का उपयोग करते हैं जब तक कि वे ठीक उसी स्टेशन पर न पहुँच जाएँ जहाँ पूर्ण पहेली रहती है।
वैश्विक (Global): एक बार जब उनके पास प्रत्येक अभाज्य संख्या के लिए पूर्ण स्थानीय टुकड़े होते हैं, तो वे उन्हें एक पूर्ण, वैश्विक एंडोमोर्फिज्म रिंग बनाने के लिए आपस में जोड़ देते हैं।

5. यह क्यों महत्वपूर्ण है

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

बड़ी उपलब्धि: यह नई विधि निश्चित (deterministic) है (यह हमेशा काम करती है, इसमें अनुमान नहीं लगाना पड़ता) और पॉलीनोमियल टाइम (polynomial time) में है (जैसे-जैसे संख्याएँ बड़ी होती हैं, यह उचित रूप से स्केल करती है)।
परिणाम: अब वे केवल कुछ शुरुआती संकेतों से गणितीय रूप से गारंटी दे सकते हैं कि वे पूर्ण "एंडोमोर्फिज्म रिंग" बना सकते हैं, बशर्ते उनके पास "डिस्क्रिमिनेंट" (अधूरेपन का माप) का गुणनखंड (factorization) हो।

सारांश

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

पुराना तरीका: बाहर निकलने का रास्ता मिलने की उम्मीद में बिना सोचे-समझे भटकते रहना।
नया तरीका: एक मानचित्र (ट्री) का उपयोग करना, दिशा जाँचने के लिए एक जादुई दिशा-सूचक यंत्र (कानी का लेम्मा) का उपयोग करना, और तुरंत यह देखने के लिए कि कौन से रास्ते बंद रास्तों की ओर ले जाते हैं, एक लेजर स्कैनर (इंटरसेक्शन थ्योरम) का उपयोग करना।

लेखकों ने केवल कुछ शुरुआती संकेतों से पूर्ण "एंडोमोर्फिज्म रिंग" को पुनर्गठित करने का एक विश्वसनीय, तेज़ और गारंटीकृत तरीका विकसित किया है। यह भविष्य की एन्क्रिप्शन प्रणालियों की सुरक्षा को समझने की दिशा में एक महत्वपूर्ण कदम है।

तकनीकी सारांश: सुपरसिंगुलर एंडोमोर्फिज्म रिंग्स की गणना करने के लिए कानी के लेम्मा और ब्रुहत-टिट्स ट्री में पाथ-फाइंडिंग को जोड़ना

समस्या विवरण
संबोधित की जाने वाली मौलिक समस्या एक सुपरसिंगुलर एलिप्टिक कर्व $E$ (जो $\mathbb{F}_{p^2}$ पर परिभाषित है) के एंडोमोर्फिज्म रिंग, $\text{End}(E)$ की नियत (deterministic) गणना करना है। जबकि साधारण कर्व्स के एंडोमोर्फिज्म रिंग की गणना के लिए हालिया बहुपद-समय (polynomial-time) प्रगति देखी गई है (GRH और फैक्टराइजेशन ओरैकल्स के तहत), सुपरसिंगुलर मामले में यह चुनौतीपूर्ण बना हुआ है। पिछले दृष्टिकोण, जैसे कि कोहेल का साइकिल-फाइंडिंग एल्गोरिदम, $O(p^{1+\epsilon})$ समय में चलता है। अधिक हालिया उप-एक्सपोनेंशियल (subexponential) एल्गोरिदम (जैसे, [EHL+20]) ह्यूरिस्टिक्स पर निर्भर करते हैं और उनके लिए इनपुट ऑर्डर का बास ऑर्डर (Bass order) होना आवश्यक है। इसके अतिरिक्त, एकल गैर-स्केलर एंडोमोर्फिज्म खोजने और पूर्ण रिंग के बीच संभाव्य बहुपद-समय (probabilistic polynomial-time) रिडक्शन मौजूद हैं (जैसे, [PW24]), लेकिन प्रतिबंधित इनपुट्स के साथ नियत (deterministic) विधियाँ सीमित रही हैं।

यह शोध पत्र एक नियत बहुपद-समय एल्गोरिदम (deterministic polynomial-time algorithm) प्रदान करने का लक्ष्य रखता है जो निम्नलिखित दिए जाने पर $\text{End}(E)$ की गणना करता है:

कर्व $E$ ।
दो गैर-कम्यूटिंग एंडोमोर्फिज्म $\alpha_1, \alpha_2$ जो एक सबऑर्डर $O_0 \subset \text{End}(E)$ उत्पन्न करते हैं।
$O_0$ के रिड्यूस्ड डिस्क्रीमिनेंट $\Delta$ का गुणनखंड (factorization)।

एल्गोरिदम की जटिलता $\log p$ , इनपुट एंडोमोर्फिज्म की डिग्री, और $\Delta/p$ के सबसे बड़े अभाज्य गुणनखंड (prime factor) के बहुपद में है।

कार्यप्रणाली (Methodology)
लेखक क्वाटरनियन अल्जेब्रा के लिए लोकल-ग्लोबल सिद्धांत (local-global principle) का लाभ उठाते हैं। चूंकि $\text{End}(E)$ , $B_{p,\infty}$ (जो $p$ और $\infty$ पर रामिफाइड है) में एक मैक्सिमल ऑर्डर है, इसलिए $\text{End}(E)$ को ग्लोबली निर्धारित करना हर उस अभाज्य $q$ पर इसके लोकल कॉम्प्लीशन $\text{End}(E) \otimes \mathbb{Z}_q$ को निर्धारित करने के समान है, जो $O_0$ के रिड्यूस्ड डिस्क्रीमिनेंट को विभाजित करता है।

कार्यप्रणाली प्रत्येक ऐसे अभाज्य $q \neq p$ के लिए दो मुख्य चरणों में आगे बढ़ती है जहाँ $O_0$ मैक्सिमल नहीं है:

लोकल एनलार्जमेंट और एम्बेडिंग (Local Enlargement and Embedding):
- एल्गोरिदम $O_0$ का एक $q$ -मैक्सिमल $q$ -एनलार्जमेंट $O_q$ (एक ऐसा ऑर्डर जो $q$ पर मैक्सिमल है लेकिन अन्य स्थानों पर $O_0$ के समान है) निर्मित करता है।
- वोइट (Voight) की तकनीकों का उपयोग करते हुए, एक आइसोमोर्फिज्म $f: O_q \otimes \mathbb{Z}_q \to M_2(\mathbb{Z}_q)$ की गणना की जाती है, जो लोकल ऑर्डर को $GL_2(\mathbb{Q}_q)$ के ब्रुहत-टिट्स ट्री (Bruhat-Tits tree) के रूट से जोड़ता है।
- लक्षित $\Lambda_E = f(\text{End}(E) \otimes \mathbb{Z}_q)$ इस ट्री में एक वर्टेक्स (vertex) है। लक्ष्य रूट से $\Lambda_E$ तक का पथ (path) खोजना है।
ब्रुहत-टिट्स ट्री में पाथ-फाइंडिंग (Path-Finding in the Bruhat-Tits Tree):
- दूरी की गणना (Distance Computation): एल्गोरिदम पहले रूट और $\Lambda_E$ के बीच की दूरी $r$ निर्धारित करता है। यह यह पता लगाकर किया जाता है कि सबसे छोटा पूर्णांक $r$ कौन सा है जिसके लिए $q^r O_q \subset \text{End}(E)$ हो। यह एक डिवीजन एल्गोरिदम (प्रपोजिशन 2.7) पर निर्भर करता है जो यह परीक्षण करता है कि क्या किसी एंडोमोर्फिज्म का एक रैशनल मल्टीपल इंटीग्रल है।
- पाथ रिकवरी (Path Recovery): एक बार जब $r$ $r$ ज्ञात हो जाता है, तो एल्गोरिदम $\Lambda_E$ $Λ_{E}$ तक जाने वाले विशिष्ट पथ (मैट्रिक्स का अनुक्रम) को पुनः प्राप्त करता है।
  - सामान्य मामला (General Case): यह चरण-दर-चरण उम्मीदवारों का परीक्षण करता है। $k$ लंबाई के एक पथ के लिए, यह एक ग्लोबल ऑर्डर का निर्माण करता है जो एक संभावित पथ के अनुदिश मैक्सिमल ऑर्डर्स के इंटरसेक्शन (intersection) के अनुरूप होता है। फिर यह जांचने के लिए डिवीजन एल्गोरिदम का उपयोग करता है कि क्या यह ग्लोबल ऑर्डर $\text{End}(E)$ के भीतर समाहित है। यदि हाँ, तो पथ आगे बढ़ता है; यदि नहीं, तो इस शाखा को काट (prune) दिया जाता है। यह इस तथ्य का उपयोग करता है कि परिमित मैक्सिमल ऑर्डर्स का इंटरसेक्शन अधिकतम तीन ऑर्डर्स के इंटरसेक्शन में बदला जा सकता है (तू का प्रमेय)।
  - बास केस (Bass Case): यदि $O_0$ , $q$ पर एक बास ऑर्डर है, तो इसे समाहित करने वाले मैक्सिमल ऑर्डर्स ट्री में एक सरल पथ बनाते हैं। एल्गोरिदम $\text{End}(E) \otimes \mathbb{Z}_q$ को कुशलतापूर्वक खोजने के लिए इस पथ के अनुदिश बाइनरी सर्च करता है।
ग्लोबल रिकंस्ट्रक्शन (Global Reconstruction):
- एक बार जब सभी प्रासंगिक $q$ के लिए लोकल मैक्सिमल ऑर्डर्स $\tilde{O}_q$ की पहचान हो जाती है, तो उन्हें मूल $O_0$ के साथ मिलाकर ग्लोबल मैक्सिमल ऑर्डर $\text{End}(E)$ बनाया जाता है।

प्रमुख तकनीकी उपकरण (Key Technical Tools)

कानी का लेम्मा और उच्च-आयामी आइसोजीनी (Kani's Lemma and Higher-Dimensional Isogenies): डिवीजन एल्गोरिदम (प्रपोजिशन 2.7) का मुख्य इंजन कानी का लेम्मा है। यह एंडोमोर्फिज्म को एक पूर्णांक से विभाजित करने की समस्या को उच्च-आयामी सेटिंग (एलिप्टिक कर्व्स के उत्पादों के बीच आइसोजीनी) में अनुवादित करने की अनुमति देता है। यह लचीलापन कुशल मूल्यांकन के लिए आवश्यक पावर्समूथनेस (powersmoothness) शर्तों को लागू करने की अनुमति देता है, एक ऐसी तकनीक जिसका उपयोग [Rob22] और [PW24] में किया गया था, लेकिन यहाँ ब्रुहत-टिट्स ट्री को नेविगेट करने के लिए नियत रूप से (deterministically) लागू किया गया है।
इंटरसेक्शन पर तू का प्रमेय (Tu's Theorem on Intersections): शोध पत्र तू [Tu11] के एक प्रमेय का उपयोग करता है जो बताता है कि $M_2(\mathbb{Q}_q)$ में किसी भी परिमित मैक्सिमल ऑर्डर्स का इंटरसेक्शन उनमें से अधिकतम तीन के इंटरसेक्शन के बराबर होता है। यह एल्गोरिदम को जटिल स्थानीय ऑर्डर्स के इंटरसेक्शन का परीक्षण करने, उनके अनुरूप ग्लोबल ऑर्डर्स का निर्माण करके और उन्हें $\text{End}(E)$ के विरुद्ध परीक्षण करके, प्रभावी रूप से एक साथ बड़ी संख्या में उम्मीदवारों को खारिज करने की अनुमति देता है।
HD प्रतिनिधित्व (HD Representation): एंडोमोर्फिज्म को "HD प्रतिनिधित्व" (टोरशन पॉइंट्स पर इमेज) का उपयोग करके दर्शाया जाता है, जो कुशल मूल्यांकन और डिग्री विश्लेषण की अनुमति देता है, जो बहुपद-समय रनटाइम के लिए महत्वपूर्ण है।

परिणाम और जटिलता (Results and Complexity)
शोध पत्र थ्योरम 1.1 प्रस्तुत करता है, जो $\log p$ , इनपुट डिग्री, और गुणनखंड के सापेक्ष $\text{End}(E)$ की गणना करने वाले एक नियत बहुपद-समय एल्गोरिदम के अस्तित्व को बताता है।

सामान्य मामला (General Case): जटिलता $\Delta/p$ को विभाजित करने वाले अभाज्य संख्याओं की संख्या और उनके सबसे बड़े अभाज्य के रैखिक (linear) में है। डिवीजन एल्गोरिदम के कॉल्स की संख्या प्रति अभाज्य $q$ के लिए $4(e_q + 2)$ द्वारा सीमित है, जहाँ $e_q = v_q(\text{discrd}(O_0))$ है।
बास केस (Bass Case): यदि इनपुट ऑर्डर $q$ पर बास है, तो बाइनरी सर्च के माध्यम से डिवीजन एल्गोरिदम के कॉल्स की जटिलता $4 \log_2(e_q + 1)$ तक सुधर जाती है।
तुलना: यह [EHL+20] से बेहतर है, जिसे बास प्रतिबंध की आवश्यकता थी और जो ह्यूरिस्टिक्स पर निर्भर था, तथा उप-एक्सपोनेंशियल समय में चलता था। यह [PW24] से भी भिन्न है क्योंकि यह नियत (deterministic) है और इसके लिए गैर-स्केलर एंडोमोर्फिज्म के लिए ओरकल की आवश्यकता नहीं है, हालांकि यह इनपुट गुणनखंडन को मानता है।

महत्व और दावे (Significance and Claims)
लेखक दावा करते हैं कि यह कार्य कोहेल के उस दृष्टिकोण को पूरा करता है जिसमें एक सबरिंग जेनरेट करना और उसे पूर्ण रिंग तक विस्तारित करना शामिल है, जिससे एक नियत समाधान मिलता है जहाँ पिछले तरीके या तो ह्यूरिस्टिक थे या संभाव्य (probabilistic) थे।

क्रिप्टोग्राफिक प्रासंगिकता: सुपरसिंगुलर एंडोमोर्फिज्म रिंग्स की गणना आइसोजीनी-आधारित क्रिप्टोसिस्टम्स (जैसे, SIDH, जो 2022 में टूट गया था) की सुरक्षा के लिए केंद्रीय है। इस समस्या की हार्डनेस इन स्कीम्स की सुरक्षा के लिए एक आवश्यक शर्त है।
मेथोडोलॉजिकल एडवांसमेंट: शोध पत्र प्रदर्शित करता है कि उच्च-आयामी आइसोजीनी (कानी के लेमा के माध्यम से) की तकनीकों का, जो मूल रूप से SIDH को तोड़ने और साधारण एंडोमोर्फिज्म रिंग्स की गणना करने के लिए विकसित की गई थीं, का उपयोग सुपरसिंगुलर कर्व्स के लिए ब्रुहत-टिट्स ट्री की संरचना को नेविगेट करने के लिए प्रभावी ढंग से किया जा सकता है।
व्यापकता (Generality): पिछले एल्गोरिदम के विपरीत जिन्हें बास ऑर्डर की आवश्यकता थी, यह विधि सामान्य ऑर्डर्स के लिए काम करती है, जो सुपरसिंगुलर एंडोमोर्फिज्म रिंग्स का विश्लेषण करने के लिए एक अधिक मजबूत उपकरण प्रदान करती है।

शोध पत्र $p=103$ के साथ एक ठोस उदाहरण प्रदान करके समाप्त होता है, जो ऑर्डर को बढ़ाने, दूरी की गणना करने और पूर्ण एंडोमोर्फिज्म रिंग को पुनर्गठित करने के लिए ब्रुहत-टिट्स ट्री में पथ को पुनः प्राप्त करने की चरण-दर-चरण प्रक्रिया को दर्शाता है।