🔢 mathematics

Computing Isomorphisms between Products of Supersingular Elliptic Curves

यह शोध पत्र एक कुशल संभाव्य लास वेगास एल्गोरिदम प्रस्तुत करता है जो, सामान्य रीमान परिकल्पना के तहत, ड्यूरिंग पत्राचार (Deuring correspondence) का लाभ उठाकर समस्या को क्वाटरनियन ऑर्डर्स (quaternion orders) पर बीजगणितीय समीकरणों को हल करने में अनुवादित करके, सुपरसिंगुलर एलिप्टिक कर्व्स के उत्पादों के बीच आइसोमॉर्फिज्म को बहुपद समय (polynomial time) में संगणित करता है।

मूल लेखक: Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer

प्रकाशित 2026-07-13

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

CC BY 4.0

मूल लेखक: Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer

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

कल्पना कीजिए कि आपके पास दो जादुई बक्से हैं, जिनमें से प्रत्येक में "सुपरसिंगुलर एलिप्टिक कर्व्स" नामक विशेष, चमकते हुए गोलों (orbs) की एक जोड़ी है। ये गोले एक बहुत ही जटिल, उच्च-आयामी आकृति के निर्माण खंड (building blocks) हैं जिसे 'एबेलियन वैरायटी' कहा जाता है। एक प्रसिद्ध गणितीय नियम जिसे 'डेलिग्ने-ओगस-शियोडा प्रमेय' (Deligne-Ogus-Shioda theorem) कहा जाता है, हमें बताता है कि भले ही ये दोनों बक्से बाहर से कितने भी अलग क्यों न दिखें, यदि वे एक ही प्रकार के जादुई गोलों से बने हैं, तो वे वास्तव में अंदर से समान हैं। यह ऐसा ही है जैसे यह कहना कि दो अलग-अलग दिखने वाले लेगो (Lego) किले वास्तव में ईंटों के एक ही सेट से बने हैं, बस उन्हें अलग तरह से व्यवस्थित किया गया है।

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

यह शोध पत्र अंततः उस मानचित्र को खोजने के बारे में है। लेखक, पियरिक गौड्रि (Pierrick Gaudry), जूलियन सुमियर (Julien Soumier), और पियरे-जीन स्पैनलेहाउर (Pierre-Jean Spaenlehauer), एक नया तरीका प्रस्तुत करते हैं जो उस रूपांतरण को स्पष्ट रूप से गणना करने में सक्षम है जो इन गोलों के एक जोड़े को दूसरे में बदल देता है। वे केवल अनुमान नहीं लगाते; वे एक चरण-दर-चरण विधि (एल्गोरिदम) प्रदान करते हैं जो कुशलतापूर्वक काम करती है, बशर्ते आप पहले से ही इन गोलों के गुप्त "ब्लूप्रिंट" (एंडोमोर्फिज्म रिंग्स) को जानते हों।

जादुई ट्रिक: ज्यामिति को बीजगणित में बदलना
लेखकों का गुप्त हथियार कुछ है जिसे "ड्यूरिंग कॉरेस्पोंडेंस" (Deuring correspondence) कहा जाता है। इसे एक सार्वभौमिक अनुवादक (universal translator) के रूप में सोचें। यह इन चमकते हुए गोलों को इधर-उधर घुमाने की कठिन ज्यामितीय समस्या को एक बहुत अधिक अनुकूल भाषा में अनुवादित करता है: "क्वाटरनियन नंबरों" (quaternion numbers) से संबंधित बीजगणित।

कल्पना कीजिए कि गोले एक 4-आयामी भूलभुलैया के माध्यम से घूम रहे हैं। भूलभुलैया में सीधे नेविगेट करने के बजाय, लेखक इस भूलभुलैया को कागज पर समीकरणों के एक सेट में बदलने के लिए अनुवादक का उपयोग करते हैं। विशेष रूप से, वे सही पथ खोजने की समस्या को द्विघाती (quadratic) और रैखिक (linear) समीकरणों के एक सिस्टम को हल करने में बदल देते हैं। यह ऐसा ही है जैसे यह महसूस करना कि एक पहाड़ पर चढ़ने के बजाय, आप बस एक गणितीय समस्या को हल कर सकते हैं जो आपको ठीक से बताती है कि शिखर कहाँ है।

नुस्खा: इसे तोड़ना
शोध पत्र दो गोलों के जोड़े (आयाम 2) के मामले पर ध्यान केंद्रित करता है, जो बड़े समूहों को संभालने के लिए आधार के रूप में कार्य करता है। उनका एल्गोरिदम दो-चरणीय नृत्य की तरह काम करता है:

पहला चरण: वे एक "मैट्रिक्स ऑफ आइसोजेनीज़" (matrix of isogenies) बनाना सीखते हैं। हमारी उपमा में, एक आइसोजेनी इन गोलों को जोड़ने वाली एक विशिष्ट प्रकार की जादुई सुरंग है। वे दिखाते हैं कि कैसे एक शुरुआती सुरंगों के सेट को लेकर एक पूर्ण, प्रतिवर्ती रूपांतरण (reversible transformation) बनाने के लिए चित्र को पूरा किया जाए।
दूसरा चरण: वे "लो-डिस्क्रिमिनेंट" (low-discriminant) उप-वलयों (subrings) के उपयोग वाला एक चतुर तरीका अपनाते हैं। कल्पना कीजिए कि कुछ गोलों में एक विशेष, सरल आंतरिक पैटर्न होता है (जैसे कि लो-डिस्क्रिमिनेंट इमेजिनरी क्वाड्रेटिक ऑर्डर)। यदि आपके पास इस सरल पैटर्न तक पहुँच है, तो आप समीकरणों को बहुत तेज़ी से हल कर सकते हैं।

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

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

वे यह भी स्पष्ट करते हैं कि वे किसी भी यादृच्छिक (random) एबेलियन वैरायटी के लिए इस समस्या को हल नहीं कर रहे हैं। वे विशेष रूप से "सुपरस्पेशल" वैरायटीज़ के लिए इसे हल कर रहे हैं, जो सुपर्सिंगुलर एलिप्टिक कर्व्स के उत्पाद हैं। वे यह भी दावा नहीं करते कि उन्होंने एक ही बड़ी छलांग में सभी आयामों के लिए समस्या को हल कर लिया है; इसके बजाय, वे 2-आयामी मामले को हल करते हैं और दिखाते हैं कि बड़े समूहों (आयाम $g \ge 2$ ) को संभालने के लिए उस समाधान को कैसे स्टैक किया जा सकता है।

प्रमाण और उपकरण
लेखकों ने केवल सिद्धांत नहीं दिया; उन्होंने एक वर्किंग प्रोटोटाइप बनाया। उन्होंने 'मैग्मा' (Magma) नामक एक कंप्यूटर अलजेब्रा सॉफ्टवेयर में अपने एल्गोरिदम को लागू किया। हालाँकि, वे सावधानीपूर्वक समझाते हैं कि उनका कोड वर्तमान में भौतिक सुरंगों के बजाय "कर्नेल आइडियल्स" (kernel ideals - सुरंगों का गणितीय विवरण) आउटपुट करता है। वास्तविक सुरंगों को प्राप्त करने के लिए, आपको एक अलग, मानक रूपांतरण चरण चलाना होगा, जिसे वे नोट करते हैं कि यह भी कुशल है।

यह शोध पत्र कठोर है। वे केवल यह सुझाव नहीं देते कि यह काम कर सकता है; वे औपचारिक प्रमाण प्रदान करते हैं कि उनकी विधि सही है और यह उस समय में चलती है जिसका वे दावा करते हैं, बशर्ते GRH सत्य हो। उन्होंने इस प्रक्रिया के दौरान नए गणितीय उपकरण भी विकसित किए, जैसे कि एक "क्वासी-लीनियर क्वाटरनियोनिक मेथड" (quasi-linear quaternionic method) जिसका उपयोग एक जादुई सुरंग को दूसरी सुरंग से विभाजित करने के लिए किया जाता है, जो समस्या के 4-आयामी गियर्स में फिट होने वाले एक विशेष रिंच (wrench) के होने जैसा है।

संक्षेप में, यह शोध पत्र एक ऐसे प्रमेय को लेता है जो कहता है कि "ये दो चीजें एक ही हैं" और उसे एक व्यावहारिक निर्देश पुस्तिका में बदल देता है कि "यहाँ बताया गया है कि यदि आपके पास शुरू करने के लिए सही चाबियाँ हैं, तो आप एक को दूसरे में बिल्कुल कैसे बदलते हैं।" यह इन जटिल गणितीय आकृतियों की छिपी हुई वास्तुकला को समझने की दिशा में एक महत्वपूर्ण कदम है, जो प्राचीन बीजगणित और आधुनिक कंप्यूटिंग शक्ति के मिश्रण का उपयोग करता है।

तकनीकी सारांश: सुपरसिंगुलर एलिप्टिक कर्व्स के उत्पादों के बीच आइसोमॉर्फिज्म की गणना करना

समस्या विवरण
यह शोध पत्र डेलिग्ने-ओगस-शियोडा (Deligne-Ogus-Shioda) प्रमेय के कम्प्यूटेशनल कार्यान्वयन को संबोधित करता है, जो यह गारंटी देता है कि किसी भी पूर्णांक $g \ge 2$ के लिए, एक परिमित क्षेत्र $\mathbb{F}_q$ पर परिभाषित सभी आयाम- $g$ सुपरस्पेशल एबेलियन वेरिएटीज़ (abelian varieties) अनपोलराइज्ड एबेलियन वेरिएटीज़ के रूप में एक दूसरे के आइसोमॉर्फिक (isomorphic) होते हैं। विशेष रूप से, लेखक समस्या 1.1 पर काम करते हैं: दिए गए सुपरसिंगुलर एलिप्टिक कर्व्स के दो सेटों $E_1, \dots, E_g$ और $E'_1, \dots, E'_g$ (जो $\mathbb{F}_q$ पर परिभाषित हैं) के लिए, उनके उत्पादों $E_1 \times \cdots \times E_g$ और $E'_1 \times \cdots \times E'_g$ के बीच एक स्पष्ट $\mathbb{F}_q$ -आइसोमॉर्फिज्म की गणना करें।

लेखक नोट करते हैं कि यह आम तौर पर एक कठिन समस्या है क्योंकि एक सुपरसिंगुलर कर्व के एंडोमोर्फिज्म रिंग (endomorphism ring) की गणना करना कठिन माना जाता है, जो कुछ क्रिप्टोग्राफिक कंस्ट्रक्शंस की सुरक्षा का आधार है। फलस्वरूप, यह कार्य इस विशिष्ट धारणा के तहत कार्य करता है कि इनपुट कर्व्स के एंडोमोर्फिज्म रिंग्स पहले से ज्ञात हैं और कुशलतापूर्वक प्रस्तुत किए गए हैं।

कार्यप्रणाली और दृष्टिकोण
यह शोध पत्र ड्यूरिंग कॉरेस्पोंडेंस (Deuring correspondence) का लाभ उठाता है, जो $\mathbb{F}_q$ पर सुपरसिंगुलर एलिप्टिक कर्व्स की श्रेणी और क्वैटरनियन एल्जेब्रा $B_{p,\infty}$ में मैक्सिमल ऑर्डर्स पर इन्वर्टिबल लेफ्ट मॉड्यूल्स की श्रेणी के बीच एक एंटी-इक्विवेलेंस स्थापित करता है। यह लेखकों को ज्योमेट्रिक समस्या (आइसोजेनी की गणना) को क्वैटरनियन ऑर्डर्स से जुड़ी एक बीजगणितीय समस्या में अनुवाद करने की अनुमति देता है।

मुख्य रणनीति नॉर्म इक्वेशंस (norm equations) से प्राप्त पूर्णांकों पर रैखिक और द्विघात समीकरणों के सिस्टम को हल करने में आइसोमॉर्फिज्म की गणना को कम करने में निहित है। दृष्टिकोण दो प्राथमिक तकनीकी स्तंभों पर निर्भर करता है:

क्वाटरनियोनिक डिवीजन (Quaternionic Division): लेखक क्वैटरनियन एल्जेब्रा के भीतर एक एंडोमोर्फिज्म को एक आइसोोजेनी द्वारा विभाजित करने के लिए एक क्वासी-लीनियर विधि (प्रपोजिशन 4.6) विकसित करते हैं। इसमें परिणामी आइडियल (ideal) का आधार खोजने के लिए $\mathbb{Z}$ पर लीनियर इक्वेशंस के सिस्टम को हल करना शामिल है।
कानी का फॉर्मूला (Kani's Formula) और कर्नेल स्थितियाँ: एक प्रमुख सैद्धांतिक योगदान एक आवश्यक और पर्याप्त मानदंड (थ्योरम 5.3) प्रदान करना है, जो यह निर्धारित करता है कि क्या आइसोमॉर्फिज्म मैट्रिक्स के पहले कॉलम के रूप में दो सेपरेबल आइसोोजेनीज़ का जोड़ा बन सकता है। यह मानदंड कर्व्स के उत्पादों के बीच आइसोोजेनी की डिग्री के लिए कानी के फॉर्मूला के एक परिष्कृत संस्करण (प्रपोजिशन 4.8) पर निर्भर करता है, जो यह सुनिश्चित करता है कि परिणामी मैप वास्तव में एक आइसोमॉर्फिज्म है, जिससे डिग्री बाधाओं (degree constraints) का सत्यापन होता है।

एल्गोरिदम आयाम $g$ पर इंडक्शन (induction) के माध्यम से आगे बढ़ता है। बेस केस ( $g=2$ ) को एल्गोरिदम 6 द्वारा संभाला जाता है, जो आइसोमॉर्फिज्म मैट्रिक्स का प्रतिनिधित्व करने वाले $2 \times 2$ मैट्रिक्स के आइसोोजेनीज का निर्माण करता है। $g > 2$ के लिए, एल्गोरिदम 1 समस्या को $(g-1)$ -डायमेंशनल आइसोमॉर्फिज्म और एक 2-डायमेंशनल आइसोमॉर्फिज्म की गणना करने में पुनरावर्ती (recursively) रूप से कम करता है।

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

पॉलिनोमियल-टाइम एल्गोरिदम: लेखक एल्गोरिदम 1 प्रस्तुत करते हैं, जो एक प्रोबेबिलिस्टिक लास वेगास (Las Vegas) एल्गोरिदम है जो वांछित आइसोमॉर्फिज्म की गणना करता है। जनरल रेडाइज्ड रिमैन हाइपोथीसिस (GRH) के तहत, एल्गोरिदम का अपेक्षित समय $g$ के सापेक्ष लीनियर और $\log(p)$ के सापेक्ष पॉलिनोमियल होता है।
स्पष्ट निर्माण (Explicit Construction): शोध पत्र ज्ञात एंडोमोर्फिज्म रिंग्स के संदर्भ में डेलिग्ने-ओगस-शियोडा प्रमेय का एक कंस्ट्रक्टिव प्रूफ प्रदान करता है। आउटपुट आइसोोजेनीज का एक $g \times g$ मैट्रिक्स है, जिसे $B_{p,\infty}$ में आइडियल्स के माध्यम से कुशलतापूर्वक प्रस्तुत किया गया है।
सबरूटीन्स (Subroutines):
- अपने पहले कॉलम को दिए गए आइसोमॉर्फिज्म मैट्रिक्स का निर्माण करने की एक विधि।
- एक ऐसी तकनीक जो $E_2 \to E'_1 \times E$ के रूप में आइसोमॉर्फिज्म की गणना करती है जब एक नॉन-स्केलर लो-डिस्क्रिमिनेंट एंडोमोर्फिज्म उपलब्ध हो।
- कार्यान्वयन: मैग्मा (Magma) में एक प्रूफ-ऑफ-कॉन्सेप्ट कार्यान्वयन प्रदान किया गया है, जो आइसोमॉर्फिज्म के क्वैटरनियोनिक भाग की गणना करता है (चार कर्नेल आइडियल्स आउटपुट करता है)। लेखक नोट करते हैं कि इन आइडियल्स से स्पष्ट आइसोोजेनीज को रिकवर करना मौजूदा एल्गोरिदम (जैसे, IdealToIsogeny) का उपयोग करके पॉलिनोमियल-टाइम कॉम्प्लेक्सिटी के साथ किया जा सकता है।

महत्व और दावे
शोध पत्र का दावा है कि यह सुपरसिंगुलर एलिप्टिक कर्व्स के उत्पादों के बीच आइसोमॉर्फिज्म को स्पष्ट रूप से कंप्यूट करने के लिए पहला कुशल एल्गोरिदम प्रदान करता है, बशर्ते एंडोमोर्फिज्म रिंग्स ज्ञात हों। लेखक अपने कार्य को उच्च-आयामी आइसोोजेनी-आधारित क्रिप्टोग्राफी के लिए एक मौलिक उपकरण के रूप में देखते हैं।

विशेष रूप से, शोध पत्र मौजूदा साहित्य के भीतर दो संभावित अनुप्रयोगों को रेखांकित करता है:

लो-डिस्क्रिमिनेंट सबरिंग्स तक पहुँच: एक सामान्य सुपरस्पेशल एबेलियन वैरायटी और ज्ञात लो-डिस्क्रिमिनेंट एंडोमोर्फिज्म सबरिंग्स (जैसे कि $E_0$ जहाँ $p \equiv 3 \mod 4$ ) वाले कर्व्स के उत्पाद के बीच आइसोमॉर्फिज्म को कंप्यूट करने की क्षमता इन सबरिंग्स तक पहुंच को सुगम बना सकती है, जो विशिष्ट क्रिप्टोग्राफिक सेटिंग्स में प्रासंगिक हैं।
पोलराइज्ड एबेलियन वेरिएटीज़ का प्रतिनिधित्व: एल्गोरिदम इबुकियामा-कात्सुरा-ओर्ट (Ibukiyama-Katsura-Oort) कॉरेस्पोंडेंस के टूलबॉक्स में योगदान देते हैं, जो $2 \times 2$ क्वैटरनियन मैट्रिसेस के माध्यम से सुपरस्पेशल प्रिंसिपलली पोलराइज्ड एबेलियन सर्फेसेस का प्रतिनिधित्व करता है। लेखक सुझाव देते हैं कि उनके तरीकों का उपयोग उन सर्फेसेस के लिए यह प्रतिनिधित्व कंप्यूट करने के लिए किया जा सकता है जो जेनस-2 कर्व्स के जैकोबियन (Jacobians) नहीं हैं।

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

इसी तरह के और पेपर