लैटिस न्यूनन

दो आयामों में जालक में लघूकरण, काले सदिश जालक के लिए दिए गए आधार हैं (नीले बिंदुओं द्वारा दर्शाए गए), लाल सदिश लघुकृत आधार हैं।

गणित में, जालक आधार लघूकरण का लक्ष्य, एक पूर्णांक जालक आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग लांबिक सदिश वाले आधार का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि समान्यतः जालक के आयाम में कम से कम घातीय होती है।

लगभग लांबिक

लगभग लांबिक की एक माप 'लांबिक दोष' है। यह आधार सदिश की लंबाई के गुणन की तुलना उनके द्वारा परिभाषित समांतर चतुर्भुज के आयतन से करता है। पूर्णतः लांबिक आधार वाले सदिश के लिए, ये मात्राएँ समान होंगी।

$n$ सदिशों के किसी विशेष आधार को आव्यूह $B$, द्वारा दर्शाया जा सकता है, जिसके स्तंभ आधार सदिश $b_{i},i=1,\ldots ,n$ हैं। पूर्ण आयामी स्थिति में जहां आधार सदिश की संख्या उनके द्वारा व्याप्त समष्टि के आयाम के बराबर होती है, यह आव्यूह वर्गाकार होता है, और मूल समांतर चतुर्भुज का आयतन इस आव्यूह के निर्धारक का पूर्ण मान $\det(B)$ होता है। यदि सदिशों की संख्या अंतर्निहित समष्टि के आयाम से कम है, तो आयतन ${\sqrt {\det(B^{T}B)}}$ है।किसी दिए गए जालक $\Lambda$ के लिए , यह आयतन किसी भी पर समान (संकेत तक) है, और इसलिए इसे जालक $\det(\Lambda )$ या जालक स्थिरांक $d(\Lambda )$ के निर्धारक के रूप में जाना जाता है।

लांबिक दोष, समानांतर चतुर्भुज आयतन द्वारा विभाजित आधार सदिश लंबाई का गुणन है,

$\delta (B)={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{\sqrt {\det(B^{T}B)}}}={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{d(\Lambda )}}$

ज्यामितीय परिभाषा से यह स्पष्ट होता है कि $\delta (B)\geq 1$ समानता के साथ वास्तविकता दोष होगा, यदि जब आधार लांबिक हों।

यदि जालक लघूकरण की समस्या को सबसे छोटे संभावित दोष के साथ आधार का पता लगाने के रूप में परिभाषित किया गया है, तो समस्या NP कठिन होती है। हालाँकि, दोष $\delta (B)\leq c$ के साथ आधार का पता लगाने के लिए बहुपद काल कलन विधि मौजूद हैं जहां c कुछ स्थिरांक है जो केवल आधार सदिश की संख्या और अंतर्निहित समष्टि के आयाम (यदि भिन्न हो) पर निर्भर करता है। यह कई व्यावहारिक अनुप्रयोगों में एक अच्छा समाधान है।

दो आयामों में

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

कलन विधि का छद्मकोड, जिसे अक्सर लैग्रेंज कलन विधि या लैग्रेंज-गॉस कलन विधि के रूप में जाना जाता है, वह इस प्रकार है,

    निविष्ट, ${\textstyle (u,v)}$ जालक के लिए एक आधार ${\textstyle L}$। मान लीजिए कि ${\textstyle ||v||\leq ||u||}$, अन्यथा उन्हें एक-दूसरे के साथ बदल दें।
    निर्गत, ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$ के साथ एक आधार ${\textstyle (u,v)}$।

    जबकि ${\textstyle ||v||<||u||}$:          

${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$ # निकटतम पूर्णांक तक पूर्णांकित करें

${\textstyle r:=u-qv}$

         ${\textstyle u:=v}$
         ${\textstyle v:=r}$

अधिक जानकारी के लिए लैग्रेंज के कलन विधि पर अनुभाग देखें।

अनुप्रयोग

जालक लघूकरण कलन विधि का उपयोग कई आधुनिक संख्या सैद्धांतिक अनुप्रयोगों में किया जाता है, जिसमें $\pi$ के लिए स्पिगोट कलन विधि का आविष्कार भी सम्मिलित है। यद्यपि सबसे छोटा आधार निर्धारित करना संभवतः एक एनपी-पूर्ण समस्या है, LLL कलन विधि जैसे कलन विधि जालक आधार लघूकरण कलन विधि जैसे कलन विधि सबसे खराब स्थिति वाले प्रदर्शन की गारंटी के साथ बहुपद समय में एक छोटा (जरूरी नहीं कि सबसे छोटा) आधार पा सकते हैं। लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिथ्म का व्यापक रूप से सार्वजनिक-कुंजी क्रिप्टोग्राफी क्रिप्टोसिस्टम के क्रिप्ट विश्लेषण में उपयोग किया जाता है।

जब पूर्णांक संबंधों को प्रतिलब्धि करने के लिए उपयोग किया जाता है, तो कलन विधि के एक विशिष्ट निविष्ट में एक संवर्धित $n\times n$ तत्समक आव्यूह अंतिम कॉलम में प्रविष्टियों के साथ पहचान आव्यूह $n$ तत्व (एक बड़े सकारात्मक स्थिरांक से गुणा किया गया $w$ उन सदिशों को दंडित करना जिनका योग शून्य नहीं है) जिनके बीच संबंध खोजा जाता है।

लगभग-लांबिक आधार की गणना के लिए एलएलएल कलन विधि का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में पूर्णांक कार्यरचना बहुपद समय में की जा सकती है।

कलन विधि

निम्नलिखित कलन विधि जालक आधारों को लघुकृत करते हैं, इन कलन विधि के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं।

वर्ष	कलन विधि	कार्यान्वयन
1773	2D जालक के लिए लैग्रेंज/गॉस लघूकरण
1982	लेनस्ट्रा-लेनस्ट्रा-लोवेज़ लघूकरण	NTL, fplll
1987	ब्लॉक कॉर्किन-ज़ोलोटारेव	NTL, fplll
1993	सीसेन लघूकरण	LLLplus