लैटिस न्यूनन

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

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

लगभग लांबिक

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

$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,v)}$ साथ ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$.

    जबकि ${\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$. यद्यपि सबसे छोटा आधार निर्धारित करना संभवतः एक एनपी-पूर्ण समस्या है, लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिदम जैसे एल्गोरिदम सबसे खराब स्थिति वाले प्रदर्शन की गारंटी के साथ बहुपद समय में एक छोटा (जरूरी नहीं कि सबसे छोटा) आधार पा सकते हैं। लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिथ्म का व्यापक रूप से सार्वजनिक-कुंजी क्रिप्टोग्राफी क्रिप्टोसिस्टम के क्रिप्ट विश्लेषण में उपयोग किया जाता है।

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

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

एल्गोरिदम

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

Year	Algorithm	Implementation
1773	Lagrange/Gauss reduction for 2D lattices
1982	Lenstra–Lenstra–Lovász reduction	NTL, fplll
1987	Block Korkine–Zolotarev	NTL, fplll
1993	Seysen Reduction	LLLplus