लैटिस न्यूनन

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

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

लगभग लांबिक

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

$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}$

अधिक जानकारी के लिए लैग्रेंज के एल्गोरिदम पर अनुभाग देखें। for further details.

अनुप्रयोग

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

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

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

कलन विधि

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

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