लैटिस न्यूनन

दो आयामों में जाली में कमी: काले वेक्टर जाली के लिए दिए गए आधार हैं (नीले बिंदुओं द्वारा दर्शाए गए), लाल वेक्टर कम आधार हैं

गणित में, जाली आधार कटौती का लक्ष्य इनपुट के रूप में एक पूर्णांक जाली (समूह) आधार दिए जाने पर छोटे, लगभग ओर्थोगोनल वैक्टर के साथ एक आधार (रैखिक बीजगणित) ढूंढना है। इसे विभिन्न एल्गोरिदम का उपयोग करके महसूस किया जाता है, जिसका चलने का समय आमतौर पर जाली के आयाम में कम से कम घातीय होता है।

लगभग ऑर्थोगोनल

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

का कोई विशेष आधार $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$ समानता के साथ यदि और केवल यदि आधार ऑर्थोगोनल है।

यदि जाली कमी की समस्या को सबसे छोटे संभावित दोष के साथ आधार खोजने के रूप में परिभाषित किया गया है, तो समस्या एनपी कठिन है. हालाँकि, दोष के साथ आधार खोजने के लिए बहुपद समय एल्गोरिदम मौजूद हैं $\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