🔢 mathematics

Explicit Factorization of $X^n-1$ over $\mathbb{Z}_{p^e}$ via Cofactor-Free Single-Seed Hensel Lifting

यह शोध पत्र एक 'आइडियल डेरिवेशन मोड्यूलो प्रिंसिपल' (Ideal Derivation Modulo Principle) और एक 'कोफैक्टर-मुक्त हेन्सेल लिफ्टिंग' (cofactor-free Hensel lifting) तकनीक को पेश करके $\mathbb{Z}_{p^e}$ पर $X^n-1$ को स्पष्ट रूप से गुणनखंडित करने के लिए एक अत्यधिक कुशल ढांचे को प्रस्तुत करता है, जो शास्त्रीय विधियों की कम्प्यूटेशनल बाधाओं को समाप्त करता है, और प्रति-परत लगभग स्थिर जटिलता तथा मौजूदा कार्यान्वयनों की तुलना में महत्वपूर्ण गति वृद्धि प्राप्त करता है।

मूल लेखक: Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang

प्रकाशित 2026-06-23

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

CC BY 4.0

मूल लेखक: Yongchao Wang, Yang Ding, Jiansheng Yang, Zhiqiu Huang

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

कल्पना कीजिए कि आपके पास एक विशेष प्रकार की धातु (वलय $\mathbb{Z}_{p^e}$ ) से बना एक विशाल, जटिल ताला है। आपका लक्ष्य उन सभी अद्वितीय चाबियों को खोजना है जो इस ताले को खोलने के लिए फिट बैठती हैं। गणित की दुनिया में, यह "ताला" एक बहुपद समीकरण ( $X^n - 1$ ) है, और इन "चाबियों" को खोजने को गुणनखंडन (factorization) कहा जाता है।

लंबे समय तक, गणितज्ञ इन चाबियों को आसानी से खोज सकते थे यदि ताला साधारण, सपाट धातु (एक परिमित क्षेत्र/finite field) से बना होता। लेकिन जब ताला मोटा और अधिक जटिल हो जाता है (एक अभाज्य घात/prime power $p^e$ से बना), तो पुराने उपकरण टूट जाते हैं। वे या तो अतिरिक्त वजन ढोने में फंस जाते हैं या ऐसे पहेली को सुलझाने में अटक जाते हैं जिसका कोई समाधान नहीं है।

यह शोध पत्र इन जटिल तालों को कुशलतापूर्वक तोड़ने के लिए एक नया, चतुर टूलकिट प्रस्तुत करता है। उन्होंने इसे कैसे किया, इसे सरल उपमाओं के माध्यम से यहाँ समझाया गया है:

1. समस्या: "भारी बैकपैक" और "बंद रास्ता"

लेखक बताते हैं कि पिछली विधियों में दो प्रमुख खामियां थीं:

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

2. समाधान: एक "बीज" और एक "जादुई रेसिपी"

लेखकों ने एक ऐसा ढांचा तैयार किया जो इन दोनों (भारी बैकपैक और बंद रास्ते) से बचता है। वे तीन तरकीबों का उपयोग करते हैं:

अ. "एकल बीज" (मास्टर की)

हर एक चाबी को शुरू से खोजने के बजाय, वे पहले केवल एक पूर्ण चाबी (एक "बीज" गुणनखंड) खोजते हैं।

उपमा: कल्पना कीजिए कि आपके पास एक मास्टर स्टैम्प (मुद्रा) है। एक बार जब आपके पास एक चाबी का डिज़ाइन आ जाता है, तो आपको हर दूसरी चाबी को हाथ से तराशने की आवश्यकता नहीं होती। आप बस उस एक डिज़ाइन को कॉपी और एडजस्ट करने के लिए एक मशीन का उपयोग करके अन्य सभी को बना सकते हैं।
यह कैसे काम करता है: वे इस एकल बीज को एक सरल परत से जटिल, मोटी परतों वाले ताले तक ले जाते हैं, जिसके लिए उन्हें अतिरिक्त "भारी बैकपैक" के डेटा की आवश्यकता नहीं होती। वे यह करने के लिए शुरुआत में केवल एक बार एक "जादुई व्युत्क्रम" (pre-calculated helper tool) को कैश (cache) करते हैं।

ब. "जादुई रेसिपी" (डिकसन रिकरेंस)

एक बार जब उनके पास बीज आ जाता है, तो उन्हें अन्य सभी चाबियाँ उत्पन्न करनी होती हैं।

उपमा: केक की रेसिपी के बारे में सोचें। यदि आप एक केक के लिए सामग्री जानते हैं, तो आप एक विशिष्ट सेट के नियमों (recurrence) का उपयोग करके एक ही आकार के एक हजार अलग-अलग केक के लिए सामग्री का पता लगा सकते हैं, बस कुछ नंबरों को बदलकर।
यह कैसे काम करता है: वे डिकसन रिकरेंस (Dickson Recurrence) नामक एक गणितीय "रेसिपी" का उपयोग करते हैं। यह रेसिपी उस एकल बीज को लेती है और "ट्रेस वैल्यूज" (एक ब्लूप्रिंट की तरह) की एक लंबी सूची बनाती है। इस ब्लूप्रिंट से, वे ताले के प्रत्येक अन्य गुणनखंड के गुणांकों (coefficients) को तुरंत पुनर्गठित कर सकते हैं।

स. "दोहरी-ट्रैक" असेंबली लाइन

अंत में, उन्हें उन ब्लूप्रिंट नंबरों को वास्तविक चाबियों में बदलना होता है।

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

3. परिणाम: गति और सरलता

शोध पत्र का दावा है कि यह नया ढांचा अविश्वसनीय रूप से तेज़ है।

गति में सुधार: उन्होंने अपने तरीके का परीक्षण मानक कंप्यूटर सॉफ़्टवेयर (जैसे SageMath) के विरुद्ध किया। उनकी विधि मानक इंजन की तुलना में 445 गुना तेज़ और उनके अपने पिछले संस्करण की तुलना में 33.5 गुना तेज़ थी।
दक्षता: ताले को मोटा करने (परिशुद्धता गहराई $e$ को बढ़ाने) की लागत गति को बहुत कम प्रभावित करती है। यह एक सीढ़ी चढ़ने जैसा है जहाँ पहले कुछ पायदान कठिन होते हैं, लेकिन एक बार ऊपर पहुँच जाने के बाद, प्रत्येक अतिरिक्त कदम के लिए समान छोटा प्रयास लगता है।

यह क्यों मायने रखता है? (शोध पत्र के अनुसार)

लेखक कहते हैं कि यह आधुनिक तकनीक के तीन विशिष्ट क्षेत्रों के लिए महत्वपूर्ण है:

पोस्ट-क्वांटम क्रिप्टोग्राफी: सुरक्षा के नए मानक, जो भविष्य के क्वांटम कंप्यूटरों से डेटा की रक्षा करेंगे, इन गणितीय संरचनाओं पर निर्भर करते हैं।
फुल्ली होमोमोर्फिक एन्क्रिप्शन (Fully Homomorphic Encryption): एन्क्रिप्टेड डेटा पर डेटा को डिक्रिप्ट किए बिना गणना करने का एक तरीका। यह विधि डेटा प्रोसेसिंग के अधिक कुशल "स्लॉट्स" की अनुमति देती है।
एल्जेब्रिक कोडिंग थ्योरी: आधुनिक संचार प्रणालियों (जैसे 5G या सैटेलाइट लिंक) के लिए बेहतर त्रुटि-सुधार कोड (error-correcting codes) डिजाइन करना।

संक्षेप में, यह शोध पत्र जटिल गणितीय तालों को तोड़ने का एक "स्मार्ट, हल्का और जाम-मुक्त" तरीका प्रदान करता है, जिससे अगली पीढ़ी की सुरक्षा और संचार के लिए आधारभूत गणित बहुत तेज़ और अधिक विश्वसनीय हो जाता है।

तकनीकी सारांश: $\mathbb{Z}_{p^e}$ पर $X^n - 1$ का स्पष्ट गुणनखंडीकरण (Explicit Factorization) हेतु कोफैक्टर-मुक्त सिंगल-सीड हेन्सेल लिफ्टिंग

1. समस्या विवरण

यह शोध पत्र $\mathbb{Z}_{p^e}$ के पूर्णांक अवशेष रिंगों (integer residue rings) पर बहुपद $X^n - 1$ के स्पष्ट गुणनखंडीकरण को संबोधित करता है, जहाँ $\gcd(n, p) = 1$ है। यह प्रक्रिया पोस्ट-क्वांटम क्रिप्टोग्राफी (विशेष रूप से ML-KEM और ML-DSA जैसे लैटिस-आधारित स्कीम्स), प्लेनटेक्स्ट स्लॉट पैकिंग से जुड़े पूर्ण होमोमोर्फिक एन्क्रिप्शन (FHE), और बीजगणितीय कोडिंग सिद्धांत (फाइनाइट चेन रिंग्स पर साइक्लिक कोड्स) के लिए मौलिक है।

यद्यपि फाइनाइट फील्ड $\mathbb{F}_p$ पर गुणनखंडीकरण अच्छी तरह से समझ लिया गया है, लेकिन इन गुणनखंडों को $\mathbb{Z}_{p^e}$ तक 'लिफ्ट' करना मौजूदा विधियों में गंभीर एल्गोरिद्मिक बाधाएं प्रस्तुत करता है:

बहुपद हेन्सेल लिफ्टिंग (Polynomial Hensel Lifting): इसके लिए $O(n)$ डिग्री के वैश्विक कोफैक्टर्स (global cofactors) को बनाए रखने और अपडेट करने की आवश्यकता होती है, जिससे प्रत्येक प्रिसिजन लेयर पर उच्च गणना लागत आती है।
बहुचर न्यूटन-हेन्सेल पुनरावृत्ति (Multivariate Newton–Hensel Iteration): यह लिफ्टिंग प्रक्रिया के दौरान सीधे कारक गुणांकों को लिफ्ट करने का प्रयास करता है, लेकिन इसके लिए प्रत्येक लेयर में एक $m \times m$ जैकोबियन मैट्रिक्स को उलटने (inverting) की आवश्यकता होती है (जहाँ $m$ कोसेट आयाम है)। $\mathbb{Z}_{p^e}$ पर, शून्य-भाजक (zero-divisors) मानक उलटने की प्रक्रिया में बाधा डालते हैं, जिससे प्रति लेयर $O(p^{(m-1)^2})$ की घातीय जटिलता के साथ व्यापक खोज (exhaustive search) करनी पड़ती है।

वर्तमान कंप्यूटर अलजेब्रा सिस्टम (जैसे SageMath) में $e > 5$ होने पर इस प्रकार के गुणनखंडीकरण के लिए सामान्य-उद्देश्य समर्थन का अभाव है, जो अक्सर NotImplementedError प्रदर्शित करते हैं।

2. कार्यप्रणाली

प्रस्तावित ढांचा एक तीन-चरणीय दृष्टिकोण के माध्यम से उपरोक्त बाधाओं को समाप्त करता है जो लिफ्टिंग प्रक्रिया से वैश्विक डिग्री $n$ को अलग करता है और जैकोबियन उलटने की आवश्यकता को समाप्त करता है।

2.1. बहुचर डिकसन पुनरावृत्ति (Multivariate Dickson Recurrence) और ट्रेस जनरेशन

ढांचा एक एकल "सीड" बहुपद से सभी अपरिमेय कारकों (irreducible factors) के पावर सम ट्रेसेस उत्पन्न करने के लिए बहुचर डिकसन पुनरावृत्ति का उपयोग करता है।

सीड खोज (Seed Discovery): $\mathbb{F}_p$ पर डिग्री $m$ का एक एकल मोनिक अपरिमेय कारक $G(X)$ पाया जाता है।
ट्रेस प्रसार (Trace Propagation): सीड के गुणांकों द्वारा परिभाषित न्यूटन-गिरार्ड पहचान (Newton–Girard identities) और एक लीनियर फीडबैक शिफ्ट रजिस्टर (LFSR) संरचना का उपयोग करके, ढांचा एक वैश्विक ट्रेस ऐरे $\{S_k\}_{k=1}^n$ उत्पन्न करता है। यह ऐरे $X^n - 1$ के गुणनखंडन में $m$ आयाम वाले सभी अपरिमेय कारकों के गुणांक संबंधी जानकारी को एनकोड करता है।
कोसेट डिस्पैच (Coset Dispatch): साइक्लोटॉमिक कोसेट्स को विभाजित करने के लिए मल्टीपल इक्वल-डिफरेंस (MED) अपघटन का उपयोग किया जाता है। एक डिस्पैच तंत्र विशिष्ट कोसेट्स के आंतरिक ट्रेसेस को पुनः प्राप्त करता है, जो फुल-रैंक मामलों ( $m_s = m$ ) और डिजेनरेट मामलों ( $m_s < m$ ) दोनों को मॉड्यूलर स्केलिंग के माध्यम से संभालता है।

2.2. आइडियल डेरिवेशन मोड्यूलो प्रिंसिपल (Ideal Derivation Modulo Principle)

यह ढांचा बहुपद आइडियल्स (polynomial ideals) से गुणनखंड निर्देशांकों (factorization coordinates) को जोड़ने वाला एक सैद्धांतिक आधार स्थापित करता है।

सिद्धांत 3 (आइडियल डेरिवेशन मोड्यूलो प्रिंसिपल): एक जेनेरिक मोनिक बहुपद $G(A, X)$ (जहाँ गुणांक $A$ अनिश्चित चर हैं) द्वारा $X^n - 1$ का बहुपद लॉन्ग डिवीजन करने पर, डिग्री $< m$ का एक शेषफल $R(A, X)$ प्राप्त होता है। इस शेषफल के गुणांक एक आइडियल $I_{n,m}$ उत्पन्न करते हैं।
महत्व: इस आइडियल के $\mathbb{F}_p$ में मूल (roots) $X^n - 1$ के अपरिमेय कारकों के गुणांकों के ठीक अनुरूप होते हैं। यह $n$ और $m$ के लिए सामान्यीकृत रूप में पिछले कार्यों का विस्तार करता है।

2.3. कोफैक्टर-मुक्त सिंगल-सीड हेन्सेल लिफ्टिंग

सीड फैक्टर को $\mathbb{F}_p$ से $\mathbb{Z}_{p^e}$ तक लिफ्ट करने के लिए, ढांचा एक कोफैक्टर-मुक्त हेन्सेल लिफ्ट (सिद्धांत 4) का उपयोग करता है।

तंत्र: वैश्विक कोफैक्टर्स को अपडेट करने या जैकोबियन उलटने के बजाय, यह विधि $\mathbb{F}_p$ पर एक बार गणना किए गए कैश किए गए बहुपद व्युत्क्रम (inverse) का उपयोग करके एकल सीड फैक्टर को उन्नत करती है।
दक्षता: यह प्रति-लेयर लिफ्टिंग लागत को $O(m^2)$ बीजगणितीय ऑपरेशन्स तक कम कर देता है, जो वैश्विक डिग्री $n$ और प्रिसिजन गहराई $e$ से स्वतंत्र है।

2.4. ड्यूल-ट्रैक गुणांक पुनर्निर्माण (Dual-Track Coefficient Reconstruction)

एक बार ट्रेसेस डिस्पैच हो जाने के बाद, ढांचा एक ड्यूल-ट्रैक रणनीति का उपयोग करके शेष कारकों के गुणांकों को पुनर्गठित करता है:

प्राथमिक ट्रैक ( $p > m$ ): स्पष्ट उलटने (explicit inversion) के लिए न्यूटन-गिरार्ड पहचानों का उपयोग करता है, क्योंकि सभी $k \le m$ के लिए $k$ , $\mathbb{Z}_{p^e}$ में व्युत्क्रम योग्य है।
फालबैक ट्रैक ( $p \le m$ ): जब $p$ , $k$ को विभाजित करता है, तो न्यूटन-गिरार्ड उलटन विफल हो जाता है। ढांचा एक कोटिएंट-रिंग गॉसियन एलिमिनेशन पद्धति पर स्विच करता है, जो $\mathbb{Z}_{p^e}[X]/\langle G_{seed}(X) \rangle$ में मूलों का प्रतिनिधित्व करता है और एक गुणांक मैट्रिक्स के लेफ्ट नल स्पेस (left null space) के लिए बहुपद को हल करता है। फ्रोबेनियस एंडोमोर्फिज्म (Frobenius endomorphism) समाधान की गारंटी देता है।

3. मुख्य योगदान

आइडियल डेरिवेशन मोड्यूलो प्रिंसिपल: एक ऐसा सामान्य सिद्धांत जो मॉड्यूलार रिमाइंडर एक्सट्रैक्शन के माध्यम से प्राप्त बहुचर डिकसन बहुपद आइडियल से सभी फैक्टर गुणांकों को विशेषता के रूप में वर्णित करता है।
कोफैक्टर-मुक्त हेन्सेल लिफ्ट: एक लिफ्टिंग एल्गोरिदम जो एक कैश किए गए व्यु इनवर्स का उपयोग करके एकल सीड फैक्टर को $\mathbb{Z}_{p^e}$ तक उन्नत करता है, जिससे वैश्विक कोफैक्टर अपडेट या जैकोबियन उलटने की आवश्यकता समाप्त हो जाती है।
ड्यूल-ट्रैक रिकंस्ट्रक्शन: ट्रेस ऐरे से फैक्टर गुणांकों को पुनः प्राप्त करने के लिए एक सुदृढ़ तंत्र, जो सभी विशेषता शासनों ( $p > m$ और $p \le m$ ) को संभालने के लिए न्यूटन-गिरार्ड उलटन को फ्रोबेनियस एंडोमोर्फिज्म के साथ जोड़ता है।

4. परिणाम और जटिलता

शोध पत्र दोनों सैद्धांतिक जटिलता सीमाएं और अनुभवजन्य मूल्यांकन प्रदान करता है:

सैद्धांतिक जटिलता: $\mathbb{Z}_{p^e}$ $Z_{p^{e}}$ पर $X^n - 1$ $X^{n} - 1$ का स्पष्ट रूप से गुणनखंड करने के लिए कुल बीजगणितीय जटिलता $O(n + m^3 \log p + e \cdot m^m)$ द्वारा सीमित है।
- $O(n)$ पद ट्रेस जनरेशन के लिए है।
- $O(m^3 \log p)$ पद सीड डिस्कवरी के लिए है।
- $O(e \cdot m^2)$ पद लिफ्टिंग प्रक्रिया के लिए है, जो प्रति लेयर लगभग स्थिर (near-constant) है।
अनुभवजन्य प्रदर्शन:
- यह ढांचा SageMath के C-बैकड FLINT/Pari इंजन (रनटाइम ऑटो-सीडिंग ओवरहेड सहित) की तुलना में 445× की गति वृद्धि (speedup) प्राप्त करता है।
- यह लेखकों की पिछली "V1" स्केलर लिफ्ट विधि की तुलना में 33.5× की गति वृद्धि प्राप्त करता है।
- विधि $e = 1000$ से अधिक प्रिसिजन डेप्थ के लिए लगभग स्थिर प्रति-लेयर लिफ्टिंग लागत को मान्य करती है।

5. महत्व

यह शोध पत्र दावा करता है कि यह उस महत्वपूर्ण अंतर को भरता है जहाँ वर्तमान कंप्यूटर अलजेब्रा सिस्टम, $e > 5$ और अनिश्चित $n$ के लिए $\mathbb{Z}_{p^e}$ पर $X^n - 1$ के गुणनखंड करने के लिए सामान्य-उद्देश्य उपकरण प्रदान करने में असमर्थ हैं। बहुचर जैकोबियन उलटन से जुड़ी घातीय बाधाओं और वैश्विक डिग्री $n$ पर निर्भरता को हटाकर, यह ढांचा सक्षम बनाता है:

पैरामीटर अन्वेषण: मनमाने प्रिसिजन डेप्थ पर FHE स्कीम्स में स्लॉट-पैकिंग मापदंडों का कुशल अन्वेषण।
उन्नत क्रिप्टोग्राफिक संरचनाएं: $q = p^e$ या सामान्य साइक्लोटॉमिक ऑर्डर वाले लैटिस स्कीम्स का समर्थन, जो वर्तमान NIST मानकों के केवल प्राइम मॉड्युली और टू की घातों तक सीमित रहने के प्रतिबंध से आगे बढ़ता है।
कोडिंग थ्योरी: फाइनाइट चेन रिंग्स पर साइक्लिक कोड्स और इडेम्पोटेंट जनरेटर का कुशल निर्माण, जो फेज-शिफ्ट कीइंग (PSK) का उपयोग करने वाले आधुनिक संचार प्रणालियों के लिए आवश्यक हैं।

यह कार्य $X^n - 1$ के गुणनखंडीकरण को केवल एक सैद्धांतिक अभ्यास के रूप में नहीं, बल्कि अगली पीढ़ी के क्रिप्टोग्राफिक और कोडिंग अनुप्रयोगों के लिए एक व्यावहारिक सक्षमकर्ता (enabler) के रूप में स्थापित करता है, जो शास्त्रीय लिफ्टिंग विधियों की "गंभीर प्रदर्शन दीवारों" को पार करता है।