Explicit Factorization of $x^{p+1}-1$ over $\mathbb{Z}_{p^e}$: A Structural Approach via Dickson Polynomials

यहाँ शोध पत्र "Explicit Factorization of $x^{p+1}-1$ over $\mathbb{Z}_{p^e}$: A Structural Approach via Dickson Polynomials" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का विवरण (Problem Statement)

यह शोध पत्र पूर्णांक अवशेष वलय (integer residue ring) $\mathbb{Z}_{p^e}$ पर $x^{p+1}-1$ के स्पष्ट गुणनखंडन (explicit factorization) की कम्प्यूटेशनल और बीजगणितीय चुनौती को संबोधित करता है, जहाँ $p$ एक विषम अभाज्य संख्या (odd prime) है और $e \geq 1$ है।

• संदर्भ: यह गुणनखंडन लीनियर कॉम्प्लीमेंट्री ड्यूअल (LCD) कोड और एंटैंगलमेंट-असिस्टेड क्वांटम एरर-करेक्टिंग कोड्स (EAQECC) के निर्माण के लिए महत्वपूर्ण है। ये कोड्स पोस्ट-क्वांटम क्रिप्टोग्राफी (हल्ल हमलों का प्रतिरोध करने के लिए) और क्वांटम संचार के लिए आवश्यक हैं।
• बाधा (The Bottleneck): पारंपरिक विधियाँ $\mathbb{F}_p$ से $\mathbb{Z}_{p^e}$ तक कारकों को 'लिफ्ट' (lift) करने के लिए हेन्सल्स लेम्मा (Hensel's Lemma) पर निर्भर करती हैं। यह प्रक्रिया स्वाभाविक रूप से पुनरावृत्ति (iterative) वाली है, जो गुणांकों (coefficients) को चरण-दर-चरण परिष्कृत करने के लिए उन्हें "ब्लैक बॉक्स" की तरह मानती है। यह प्रक्रिया कम्प्यूटेशनल रूप से महंगी है (आमतौर पर $O(p^2)$ या उससे अधिक) और अंतर्निहित बीजगणितीय संरचना को अस्पष्ट कर देती है।
• लक्ष्य: लिफ्टिंग प्रक्रिया और एक विशिष्ट बीजगणितीय पैटर्न के बीच एक नियत (deterministic), संरचनात्मक संबंध की खोज करके इन पुनरावृत्ति अनुमानों को दरकिनार करना, जिससे रैखिक-समय (linear-time) गुणनखंडन सक्षम हो सके।

2. कार्यप्रणाली (Methodology)

लेखक एक नया ढांचा प्रस्तावित करते हैं जो सामान्य बहुपद लिफ्टिंग के स्थान पर डिक्सन पॉलिनोमिअल्स (Dickson polynomials) पर आधारित एक संरचनात्मक समरूपता (structural isomorphism) का उपयोग करता है।

A. बेस लेयर जनरेशन (Over $\mathbb{F}_p$)

गुणलकों की खोज करने के बजाय, अपरिमेय कारकों (irreducible factors) के गुणांकों को नियत रूप से जनरेट किया जाता है:

• $\mathbb{F}_p$ पर $x^{p+1}-1$ का गुणनखंडन रैखिक कारकों $(x \pm 1)$ और द्विघात कारकों $(x^2 - A_i x + 1)$ से मिलकर बना है।
• गुणांक $A_i$, प्रिमिटिव $(p+1)$-वें रूट ऑफ यूनिटी के ट्रेसेस (traces) हैं।
• डिक्सन पॉलिनोमिअल्स $D_n(x, \gamma)$ का उपयोग करते हुए, लेखक दिखाते हैं कि इन गुणांकों को $\mathbb{F}_p$ पर एक प्रिमिटिव बहुपद से प्राप्त एक एकल 'सीड' (seed) से पुनरावर्ती (recursively) रूप से जनरेट किया जा सकता है। विशेष रूप से, $A_i = D_i(A_1, 1)$।

B. संरचनात्मक लिफ्टिंग तंत्र ($V(x)$)

मुख्य नवाचार एक सहायक बहुपद $V(x)$ की शुरूआत है जो लिफ्टिंग प्रक्रिया को नियंत्रित करता है:

• सममिति चर (Symmetry Variable): सीधे $A_i$ को लिफ्ट करने के बजाय, लेखक एक संरचनात्मक चर $S_i = 2 - A_i^2$ को परिभाषित करते हैं।
• बहुपद $V(x)$: उन्होंने खोजा कि $S_i$ को $\mathbb{Z}_{p^h}$ से $\mathbb{Z}_{p^{h+1}}$ तक लिफ्ट करने की स्थिति $\mathbb{Z}_{p^h}$ में एक विशिष्ट बहुपद $V(x)$ के मूल (roots) खोजने के समरूप (isomorphic) है।
• $V(x)$ के गुणांक: $V(x)$ के गुणांक यादृच्छिक नहीं हैं; वे द्विपद गुणांकों (binomial coefficients) पर आधारित एक सटीक पैटर्न (पास्कल त्रिकोण से संबंधित एक "गुणांक त्रिभुज") का पालन करते हैं, जो केवल अभाज्य $p$ द्वारा निर्धारित होते हैं।
  • यदि $p = 4k+3$ है, तो $V(x)$ में विशिष्ट सम/विषम पद संरचना होती है।
  • यदि $p = 4k+1$ है, तो संरचना तदनुसार समायोजित होती है।
• एल्गोरिदम: लिफ्टिंग एक सरल स्केलर पुनरावृत्ति (scalar recurrence) बन जाती है:
  $$S^{(h+1)}_i = S^{(h)}_i + u_i \cdot \frac{V(S^{(h)}_i)}{p^h} \pmod{p^{h+1}}$$
  जहाँ $u_i$ एक पूर्व-निर्धारित अपरिवर्तनीय (invariant) है। यह बहुपद विभाजन और मैट्रिक्स ऑपरेशन्स को पूरी तरह से समाप्त कर देता है।

C. डिक्सन-इंजन (The Dickson-Engine)

इस सिद्धांत के आधार पर, लेखकों ने Dickson-Engine विकसित किया, जो एक C++ कार्यान्वयन है:

1. डिक्सन पुनरावृत्ति का उपयोग करके सीड गुणांक उत्पन्न करता है।
2. $V(x)$ का उपयोग करके संरचनात्मक चरों $S_i$ को लिफ्ट करता है।
3. रिंग पर न्यूटन के मेथड (Newton's method) के माध्यम से अंतिम गुणांक $A_i$ को पुनः प्राप्त करता है।
4. रैखिक समय जटिलता (Linear time complexity) $O(e \cdot p)$ प्राप्त करता है।

3. मुख्य योगदान (Key Contributions)

1. संरचनात्मक समरूपता (Structural Isomorphism): सिद्ध किया कि $\mathbb{Z}_{p^e}$ पर $x^{p+1}-1$ का गुणनखंडन सख्ती से एक निश्चित सहायक बहुपद $V(x)$ के मूलों द्वारा शासित होता है, जो सभी विषम अभाज्य संख्याओं के लिए गुणनखंड तर्क को एकीकृत करता है।
2. रैखिक-समय एल्गोरिदम: $O(e \cdot p)$ की जटिलता वाला एक एल्गोरिदम विकसित किया, जो मानक पुस्तकालयों (जैसे NTL का $O(p^2)$ या अधिक) की तुलना में कई गुना तेज़ है।
3. ओपन-सोर्स टूल: Dickson-Engine को जारी किया, जो मानक गुणनखंडन विधियों की तुलना में >300x की गति वृद्धि प्रदर्शित करता है।
4. कोड निर्माण: $\mathbb{Z}_{13^2}$ पर लंबाई $n=182$ के साथ निकट-इष्टतम (near-optimal) LCD कोड्स का निर्माण सफलतापूर्वक किया।

4. प्रयोगात्मक परिणाम (Experimental Results)

लेखकों ने अपने इंजन को $\mathbb{Z}_{169}$ ($p=13, e=2$) पर कोड बनाने के लिए लागू किया और ग्रे मैप (Gray map) का उपयोग करके उन्हें $\mathbb{F}_{13}$ पर मैप किया।

• प्रदर्शन:
  • $p \approx 10,000$ के लिए, डिक्सन-इंजन ने $<0.02$ सेकंड लिया, जबकि NTL ने $>5$ सेकंड लिए।
  • लिफ्टिंग लागत परिशुद्धता (precision) $e$ के साथ रैखिक रूप से बढ़ती है।
• कोड पैरामीटर्स:
  • $[182, 1, 168]_{13}$ और $[182, 2, 144]_{13}$ जैसे पैरामीटर्स वाले कोड बनाए, जो ग्रीस्मर बाउंड (Griesmer Bound) के सापेक्ष निकट-इष्टतम हैं।
  • "रोबस्टनेस प्लेटो" (The Robustness Plateau): एक आश्चर्यजनक खोज जहाँ आयाम $k$ के 4 से 12 तक तीन गुना होने पर भी न्यूनतम दूरी $d$ स्थिर $d=120$ पर बनी रही।
• डिज़ाइन अंतर्दृष्टि (Symmetry Breaking):
  • लेखकों ने पाया कि जेनरेटर बहुपद की संयुग्मी सममिति (conjugate symmetry) को तोड़ने से (ऐसे कारकों का चयन करना जो पूर्ण जोड़े नहीं हैं) वास्तव में न्यूनतम दूरी बढ़ जाती है।
  • सममित चयन कम-भार वाले कोडवर्ड (कम $d$) वाले विरल (sparse) बहुपद प्रदान करते हैं।
  • असममित (टूटी हुई) चयन बेहतर त्रुटि सुधार (उच्च $d$) वाले सघन (dense) बहुपद प्रदान करती है।

5. महत्व और निहितार्थ (Significance and Implications)

• क्रिप्टोग्राफिक सुरक्षा: इन बहुपदों को तेजी से और स्पष्ट रूप से गुणनखंड करने की क्षमता, हॉल हमलों (hull attacks) के विरुद्ध लैटिस-आधारित और LCD-आधारित पोस्ट-क्वांटम क्रिप्टोसिस्टम की सुरक्षा का विश्लेषण करने के लिए एक शक्तिशाली उपकरण प्रदान करती है।
• क्वांटम एरर करेक्शन: उनके द्वारा निर्मित कोड्स का 'हॉल डायमेंशन' (hull dimension) शून्य ($c=0$) है, जो उन्हें एंटैंगलमेंट-असिस्टेड क्वांटम एरर-करेक्टिंग कोड्स (EAQECC) के लिए आदर्श बनाता है जो एंटैंगलमेंट संसाधनों का उपभोग नहीं करते हैं।
• सैद्धांतिक बदलाव: यह कार्य बहुपद गुणनखंडन को एक नियमित संख्यात्मक गणना से बदलकर आंतरिक रिंग सममिति के अध्ययन में बदल देता है, जो क्वांटम युग के लिए एक पारदर्शी बीजगणितीय उपकरण प्रदान करता है।
• भविष्य की दिशाएं: लेखक इस "संरचनात्मक लिफ्टिंग" ढांचे को सामान्य साइक्लोटोमिक पॉलिनोमिअल्स $\Phi_n(x)$ और उच्च-क्रम रिंग्स ($e \geq 3$) तक विस्तारित करने का सुझाव देते हैं।

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