Deterministic and Efficient Ideal Arithmetic via Two-Element Representations

तकनीकी सारांश: दो-तत्व निरूपण के माध्यम से नियतात्मक और कुशल आदर्श अंकगणित

समस्या विवरण
कंप्यूटेशनल नंबर थ्योरी और पोस्ट-क्वांटम क्रिप्टोग्राफी (विशेष रूप से रिंग लर्निंग-विथ-एरर्स, या RLWE) में, कुशल आदर्श अंकगणित (ideal arithmetic) आवश्यक है। जबकि यह एक ज्ञात सैद्धांतिक तथ्य है कि किसी संख्या क्षेत्र $K$ में कोई भी भिन्नात्मक आदर्श (fractional ideal), उसके पूर्णांकों के वलय (ring of integers) $\mathcal{O}_K$ पर दो तत्वों द्वारा जनरेट किया जा सकता है, ऐसे निरूपण को खोजना कम्प्यूटेशनल रूप से चुनौतीपूर्ण है। मौजूदा एल्गोरिदम या तो यादृच्छिक (randomized) हैं या बड़े क्रिप्टोग्राफिक इनपुट के लिए अव्यावहारिक हैं क्योंकि वे आदर्शों के नॉर्म्स (norms) या परिभाषित बहुपद के डिस्क्रिमिनेन्ट (discriminant) के महंगे अभाज्य गुणनखंडन (prime factorization) पर निर्भर करते हैं। इसके अलावा, यह निर्धारित करना कि क्या कोई आदर्श मुख्य (principal) है (एकल तत्व द्वारा जनरेट किया गया है), एक खुला प्रश्न बना हुआ है जिसके लिए कोई ज्ञात कुशल एल्गोरिदम नहीं है।

विशिष्ट समस्या जिसे संबोधित किया गया है: $\mathcal{O}_K$ में एक आदर्श, जो जनरेटरों के एक सेट द्वारा परिभाषित है (अक्सर एक $\mathbb{Z}$-आधार या टुपल $(N, a(\alpha), b(\alpha))$ से प्राप्त होता है जहाँ $N$ एक बड़ा भाज्य पूर्णांक है), ऐसे दो तत्व $M, c(\alpha)$ खोजें जिससे वह आदर्श $M\mathcal{O}_K + c(\alpha)\mathcal{O}_K$ द्वारा जनरेट किया गया हो। लेखक कठिन मामले पर ध्यान केंद्रित करते हैं जहाँ $N$ एक बड़ा भाज्य (composite) नंबर है जिसमें छोटे अभाज्य गुणनखंड नहीं हैं, जिससे गुणनखंडन करना कठिन हो जाता है।

कार्यप्रणाली
यह शोध पत्र एक नियतात्मक बहुपद-समय (deterministic polynomial-time) एल्गोरिदम का प्रस्ताव करता है जो अभाज्य आदर्श गुणनखंडन और यादृच्छिकता से बचता है। दृष्टिकोण तीन चरणों में विभाजित है, जो $\mathbb{Z}/N\mathbb{Z}$ पर बहुपद अंकगणित और डेडेकिंड मानदंड (Dedekind criterion) के एक सामान्य संस्करण पर अत्यधिक निर्भर है।

1. चरण 1: आदर्श गुणनखंडन और सामान्यीकरण (Ideal Factorization and Normalization)
   एल्गोरिदम $\mathbb{Z}/N\mathbb{Z}$ पर बहुपदों पर यूक्लिडियन-शैली के एल्गोरिदम का उपयोग करके इनपुट आदर्श $(N, a(\alpha), b(\alpha))$ को कम करने का प्रयास करता है।

• यदि अग्रणी गुणांक (leading coefficients) $\mathbb{Z}/N\mathbb{Z}$ में यूनिट्स हैं, तो एल्गोरिदम बहुपदों के महत्तम समापवर्तक (GCD) की गणना करता है, जिससे आदर्श दो-तत्व रूप $(N, c(\alpha))$ में बदल जाता है।
• यदि एक गैर-तुच्छ शून्य विभाजक (non-trivial zero divisor) मिलता है (जो दर्शाता है कि $N$ भाज्य है), तो एल्गोरिदम $N$ को सह-अभाज्य घटकों में विभाजित करता है और परिणामी आदर्शों को पुनरावर्ती रूप से प्रोसेस करता है।
• उन मामलों के लिए जहाँ $N$ एक पूर्ण घात ($N = N_0^e$) है, एल्गोरिदम एक अपवाद स्थिति को संभालता है जहाँ वह $(N^e, a_1(x), N d_1(x), \dots)$ के रूप में एक आदर्श उत्पन्न करने के लिए यूक्लिडियन एल्गोरिदम चलाता है। इसके बाद, यह सुनिश्चित करने के लिए परिभाषित बहुपद $f(x)$ का उपयोग करता है कि $a_1(x)$, $f(x)$ का एक गुणनखंड हो modulo $N$।
• इस चरण का आउटपुट "विशेष रूपों" में आदर्शों का एक उत्पाद है: या तो सरल दो-तत्व आदर्श $(N_i, a_i(\alpha))$ या एक विशिष्ट संरचना वाले आदर्श जिनमें $N$ की घातें और कई जनरेटर शामिल हैं।

2. चरण 2: विशेष रूपों को संभालना और गुणन (Handling Special Forms and Multiplication)
   यह चरण $(N^e, a(\alpha), N I)$ के रूप के आदर्शों को संबोधित करता है जहाँ $N$ पूर्ण घात नहीं है।

• सामान्यीकृत डेडेकिंड मानदंड (Generalized Dedekind Criterion): एक प्रमुख तकनीकी योगदान एक सामान्यीकृत डेडेकिंड मानदंड (लेम्मा 5 और प्रमेय 3) है। यह एल्गोरिदम को एक मोनिक बहुपद $\tilde{a}(x)$ खोजने की अनुमति देता है ताकि $f(x) = \tilde{f}_1(x)N + \tilde{a}(x)A(x)$ हो, जिसमें विशिष्ट सह-अभाज्य स्थितियाँ $(\tilde{a}(x), \tilde{f}_1(x), N) = 1$ हों।
• आदर्श विभाजन और गुणन: इस रूप का उपयोग करते हुए, एल्गोरिदम एक तत्व $\bar{a}(\alpha)$ का निर्माण करता है ताकि $\tilde{a}(\alpha)\bar{a}(\alpha) \equiv N \pmod{N^s}$ हो। यह गुण आदर्शों के कुशल विभाजन और दो-तत्व निरूपण में आदर्शों के गुणन को सक्षम बनाता है। विशेष रूप से, यह सिद्ध करता है कि $(N, \tilde{a}_1(\alpha))(N, \tilde{a}_2(\alpha)) = (N^2, \tilde{a}_1(\alpha)\tilde{a}_2(\alpha))$, बशर्ते कि जनरेटर सामान्यीकृत डेडेकिंड स्थिति को संतुष्ट करते हों।
• एल्गोरिदम जटिल आदर्शों को सरल दो-तत्व आदर्शों $(N_i, \tilde{a}_i(\alpha))$ के उत्पादों में पुनरावर्ती रूप से कम करता है।

3. चरण 3: चाइनीज रिमाइंडर थ्योरम के माध्यम से पुनर्संयोजन (Reassembly via Chinese Remainder Theorem)
   एक बार जब इनपुट आदर्श को सह-अभाज्य दो-तत्व आदर्शों $(N_i, a_i(\alpha))$ के एक उत्पाद में विभाजित कर दिया जाता है, तो एल्गोरिदम उन्हें एक एकल दो-तत्व निरूपण $(M, c(\alpha))$ में जोड़ने के लिए चाइनीज रिमाइंडर थ्योरम (लेम्मा 2) का उपयोग करता है।

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

• नियतात्मक बहुपद-समय एल्गोरिदम: शोध पत्र मोनोजेनिक क्षेत्रों (monogenic fields) में आदर्शों के लिए दो-तत्व निरूपण खोजने के लिए पहला नियतात्मक एल्गोरिदम प्रस्तुत करता है (और गैर-मोनोजेनिक क्षेत्रों में जहाँ आदर्श का नॉर्म इंडेक्स $[\mathcal{O}_K : \mathbb{Z}[x]/(f)]$ के साथ सह-अभाज्य है), जिसमें नॉर्म के अभाज्य गुणनखंडन की आवश्यकता नहीं होती है।
• सामान्यीकृत डेडेकिंड मानदंड: लेखक एक सामान्यीकृत डेडेकिंड मानदंड पेश करते हैं जो भाज्य मापांक (composite moduli) $N$ के लिए कार्य करता है। यह उपयुक्त बहुपद जनरेटरों की पहचान करने की अनुमति देता है जो $N$ के अभाज्य गुणनखंडों को जाने बिना कुशल आदर्श गुणन और विभाजन की सुविधा प्रदान करते हैं।
• भाज्य मापांक को संभालना: पिछले तरीकों (जैसे पोहस्ट-ज़ासेनहॉस) के विपरीत, जो अभाज्य गुणनखंडों पर निर्भर करते हैं, यह विधि सीधे भाज्य $N$ को संभालती है। यह प्रदर्शित करता है कि केवल निरूपण खोजने के लिए $N$ के गुणनखंडों को खोजना आवश्यक नहीं है और वास्तव में यह प्रक्रिया को धीमा कर देता है।
• दक्षता: एल्गोरिदम अभिन्न मैट्रिसेस (लैटिस) पर महंगी गणनाओं के स्थान पर बहुपदों पर अंकगणित का उपयोग करता है, जिससे बड़े इनपुट के लिए स्पेस और टाइम कॉम्प्लेक्सिटी काफी कम हो जाती है।

परिणाम और जटिलता
मुख्य परिणाम (प्रमेय 1) बताता है कि डिग्री $n$ के एक मोनोजेनिक क्षेत्र के लिए, दो-तत्व निरूपण समस्या को $\text{poly}(n, \log N)$ समय में हल किया जा सकता है।

• जब $N$ वर्ग-मुक्त (square-free) होता है, तो जटिलता $O(n^2 \log N \cdot \omega(N))$ होती है, जहाँ $\omega(N)$ $N$ के अलग-अलग अभाज्य गुणनखंडों की संख्या है। चूंकि $\omega(N)$ औसतन $\log \log N$ होता है, इसलिए जटिलता यादृच्छिक एल्गोरिदम के तुल्य है लेकिन नियतात्मक है।
• एल्गोरिदम मोनोजेनिक बहुपदों के लिए व्यावहारिक है, जिनमें साइक्लोटोमिक बहुपदों (cyclotomic polynomials) को शामिल किया गया है जिनका उपयोग लैटिस-आधारित क्रिप्टोग्राफी (जैसे NewHope, Crystals-Kyber) में व्यापक रूप से किया जाता है।
• यदि एल्गोरिदम निरूपण बनाने में विफल रहता है, तो यह एक प्रमाण (certificate) प्रदान करता है कि क्षेत्र मोनोजेनिक नहीं है (या इंडेक्स की शर्त पूरी नहीं होती है)।

महत्व और दावे
शोध पत्र यह दावा करता है कि अभाज्य गुणनखंडन और यादृच्छिकता पर निर्भरता को हटाकर आदर्श अंकगणित की लंबे समय से चली आ रही अक्षमता को हल किया गया है।

• क्रिप्टोग्राफिक प्रासंगिकता: यह कार्य आइडियल लैटिस पर आधारित पोस्ट-क्वांटम क्रिप्टोग्राफिक स्कीम्स के कार्यान्वयन का सीधा समर्थन करता है, विशेष रूप से वे जो साइक्लोटोमिक क्षेत्रों का उपयोग करते हैं।
• सैद्धांतिक प्रगति: यह पोहस्ट-ज़ासेनहॉस एल्गोरिदम को सामान्य बनाता है (जो अभाज्य नॉर्म्स तक सीमित था) जिसे मनमाने भाज्य पूर्णांकों के लिए विस्तारित किया गया है।
• विनम्रता: लेखक नोट करते हैं कि हालांकि यह एल्गोरिदम सभी मोनोजेनिक क्षेत्रों के आदर्शों के लिए काम करता है, गैर-मोनोजेनिक क्षेत्रों में इसे लागू करने के लिए आदर्श का नॉर्म इंडेक्स के साथ सह-अभाज्य होना चाहिए। उन्होंने एक खुला प्रश्न भी पहचाना है: दिए गए संख्या क्षेत्र के लिए बहुपद समय में एक मोनोजेनिक बहुपद निरूपण खोजना, जो वर्तमान में 'इनessential discriminant divisors' के कारण बाधित है। शोध पत्र यह दावा नहीं करता है कि यह सामान्य मुख्य आदर्श समस्या (principal ideal problem) या बड़े पूर्णांकों के गुणनखंडन को हल करता है, बल्कि यह आदर्श निरूपण के विशिष्ट कार्य के लिए इन कठिन समस्याओं को दरकिनार करता है।