लैटिस न्यूनन: Difference between revisions

Revision as of 07:42, 13 July 2023

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

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

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

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

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

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

दो आयामों में

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

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

    निविष्ट:  ${\textstyle (u,v)}$  जालक के लिए एक आधार  ${\textstyle L}$ . ये मान लीजिए  ${\textstyle ||v||\leq ||u||}$ , अन्यथा उन्हें स्वैप करें।
    आउटपुट: एक आधार  ${\textstyle (u,v)}$  साथ  ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$ .

    जबकि  $| | v | | <$

@@ Line 1: / Line 1: @@
-[[Image:Lattice-reduction.svg|thumb|right|300px|दो आयामों में जालक में कमी: काले वेक्टर जालक के लिए दिए गए आधार हैं (नीले बिंदुओं द्वारा दर्शाए गए), लाल वेक्टर कम आधार हैं]]गणित में, जालक आधार लघूकरण का लक्ष्य, एक पूर्णांक गणितीय आधार के साथ दिए गए इनपुट के रूप में
+[[Image:Lattice-reduction.svg|thumb|right|300px|दो आयामों में जालक में लघूकरण, काले सदिश जालक के लिए दिए गए आधार हैं (नीले बिंदुओं द्वारा दर्शाए गए), लाल सदिश लघुकृत आधार हैं।]]गणित में, '''जालक आधार लघूकरण''' का लक्ष्य, एक पूर्णांक [[जाली (समूह)|जालक]] आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग [[ ओर्थोगोनल |लांबिक]] सदिश वाले [[आधार (रैखिक बीजगणित)|आधार]] का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि  समान्यतः जालक के आयाम में कम से कम घातीय होती है।
-इनपुट के रूप में एक पूर्णांक [[जाली (समूह)|जालक]] आधार दिए जाने पर छोटे, लगभग [[ ओर्थोगोनल |ओर्थोगोनल]] वैक्टर के साथ एक [[आधार (रैखिक बीजगणित)|आधार]] ढूंढना है। इसे विभिन्न एल्गोरिदम का उपयोग करके महसूस किया जाता है, जिसका चलने का समय आमतौर पर जालक के आयाम में कम से कम घातीय होता है।
 ==लगभग ऑर्थोगोनल==
-लगभग ऑर्थोगोनल का एक माप 'ऑर्थोगोनैलिटी दोष' है। यह आधार वैक्टर की लंबाई के उत्पाद की तुलना उनके द्वारा परिभाषित समांतर चतुर्भुज के आयतन से करता है। पूर्णतः ऑर्थोगोनल आधार वाले वैक्टर के लिए, ये मात्राएँ समान होंगी।
+लगभग ऑर्थोगोनल का एक माप 'ऑर्थोगोनैलिटी दोष' है। यह आधार सदिश की लंबाई के उत्पाद की तुलना उनके द्वारा परिभाषित समांतर चतुर्भुज के आयतन से करता है। पूर्णतः ऑर्थोगोनल आधार वाले सदिश के लिए, ये मात्राएँ समान होंगी।
-का कोई विशेष आधार <math>n</math> वैक्टर को मैट्रिक्स द्वारा दर्शाया जा सकता है (गणित) <math>B</math>, जिनके कॉलम आधार वेक्टर हैं <math>b_i, i = 1, \ldots, n</math>. पूर्ण आयामी मामले में जहां आधार वैक्टर की संख्या उनके द्वारा व्याप्त स्थान के आयाम के बराबर होती है, यह मैट्रिक्स वर्गाकार होता है, और मौलिक समांतर चतुर्भुज का आयतन इस मैट्रिक्स के निर्धारक का पूर्ण मान होता है <math>\det(B)</math>. यदि सदिशों की संख्या अंतर्निहित स्थान के आयाम से कम है, तो आयतन है <math>\sqrt{\det(B^T B)}</math>. किसी दिए गए जालक के लिए <math>\Lambda</math>, यह आयतन किसी भी आधार के लिए समान (हस्ताक्षर तक) है, और इसलिए इसे जालक के निर्धारक के रूप में जाना जाता है <math>\det(\Lambda)</math> या जालक स्थिरांक <math>d(\Lambda)</math>.
+का कोई विशेष आधार <math>n</math> सदिश को मैट्रिक्स द्वारा दर्शाया जा सकता है (गणित) <math>B</math>, जिनके कॉलम आधार सदिश हैं <math>b_i, i = 1, \ldots, n</math>. पूर्ण आयामी मामले में जहां आधार सदिश की संख्या उनके द्वारा व्याप्त स्थान के आयाम के बराबर होती है, यह मैट्रिक्स वर्गाकार होता है, और मौलिक समांतर चतुर्भुज का आयतन इस मैट्रिक्स के निर्धारक का पूर्ण मान होता है <math>\det(B)</math>. यदि सदिशों की संख्या अंतर्निहित स्थान के आयाम से कम है, तो आयतन है <math>\sqrt{\det(B^T B)}</math>. किसी दिए गए जालक के लिए <math>\Lambda</math>, यह आयतन किसी भी आधार के लिए समान (हस्ताक्षर तक) है, और इसलिए इसे जालक के निर्धारक के रूप में जाना जाता है <math>\det(\Lambda)</math> या जालक स्थिरांक <math>d(\Lambda)</math>.
-ऑर्थोगोनैलिटी दोष, समानांतर चतुर्भुज आयतन द्वारा विभाजित आधार वेक्टर लंबाई का उत्पाद है;
+ऑर्थोगोनैलिटी दोष, समानांतर चतुर्भुज आयतन द्वारा विभाजित आधार सदिश लंबाई का उत्पाद है;
 :<math>\delta(B) = \frac{\Pi_{i=1}^n \|b_i\|}{\sqrt{\det(B^T B)}} = \frac{\Pi_{i=1}^n \|b_i\|}{d(\Lambda)}</math>
 ज्यामितीय परिभाषा से इसकी सराहना की जा सकती है <math>\delta(B) \ge 1</math> समानता के साथ यदि और केवल यदि आधार ऑर्थोगोनल है।
-यदि जालक कमी की समस्या को सबसे छोटे संभावित दोष के साथ आधार खोजने के रूप में परिभाषित किया गया है, तो समस्या [[ एनपी कठिन ]] है {{Citation needed|reason=This seems too strong, as, for example the Shortest Vector Problem is only known to be NP-hard under randomized reductions.|date=July 2022}}. हालाँकि, दोष के साथ आधार खोजने के लिए बहुपद समय एल्गोरिदम मौजूद हैं <math>\delta(B) \le c</math> जहां c कुछ स्थिरांक है जो केवल आधार वैक्टर की संख्या और अंतर्निहित स्थान के आयाम पर निर्भर करता है (यदि भिन्न हो){{Citation needed|date=July 2022}}. कई व्यावहारिक अनुप्रयोगों में यह एक अच्छा समाधान है{{Citation needed|date=July 2022}}.
+यदि जालक कमी की समस्या को सबसे छोटे संभावित दोष के साथ आधार खोजने के रूप में परिभाषित किया गया है, तो समस्या [[ एनपी कठिन ]] है {{Citation needed|reason=This seems too strong, as, for example the Shortest Vector Problem is only known to be NP-hard under randomized reductions.|date=July 2022}}. हालाँकि, दोष के साथ आधार खोजने के लिए बहुपद समय एल्गोरिदम मौजूद हैं <math>\delta(B) \le c</math> जहां c कुछ स्थिरांक है जो केवल आधार सदिश की संख्या और अंतर्निहित स्थान के आयाम पर निर्भर करता है (यदि भिन्न हो){{Citation needed|date=July 2022}}. कई व्यावहारिक अनुप्रयोगों में यह एक अच्छा समाधान है{{Citation needed|date=July 2022}}.
 ==दो आयामों में==
-केवल दो वैक्टरों से युक्त आधार के लिए, दो पूर्णांकों के सबसे बड़े सामान्य विभाजक के लिए यूक्लिडियन एल्गोरिदम के अनुरूप लघूकरण की एक सरल और कुशल विधि है। [[ यूक्लिडियन एल्गोरिथ्म ]] की तरह, विधि पुनरावृत्तीय है; प्रत्येक चरण में छोटे वेक्टर के पूर्णांक गुणज को जोड़कर या घटाकर दो वेक्टरों में से बड़े को कम किया जाता है।
+केवल दो सदिशों से युक्त आधार के लिए, दो पूर्णांकों के सबसे बड़े सामान्य विभाजक के लिए यूक्लिडियन एल्गोरिदम के अनुरूप लघूकरण की एक सरल और कुशल विधि है। [[ यूक्लिडियन एल्गोरिथ्म ]] की तरह, विधि पुनरावृत्तीय है; प्रत्येक चरण में छोटे सदिश के पूर्णांक गुणज को जोड़कर या घटाकर दो सदिशों में से बड़े को कम किया जाता है।
 एल्गोरिथ्म का छद्मकोड, जिसे अक्सर लैग्रेंज एल्गोरिदम या लैग्रेंज-गॉस एल्गोरिदम के रूप में जाना जाता है, इस प्रकार है:
-      इनपुट: <math display="inline"> (u,v) </math> जालक के लिए एक आधार <math display="inline"> L</math>. ये मान लीजिए <math display="inline"> ||v|| \leq ||u|| </math>, अन्यथा उन्हें स्वैप करें।
+      निविष्ट: <math display="inline"> (u,v) </math> जालक के लिए एक आधार <math display="inline"> L</math>. ये मान लीजिए <math display="inline"> ||v|| \leq ||u|| </math>, अन्यथा उन्हें स्वैप करें।
       आउटपुट: एक आधार <math display="inline"> (u,v) </math> साथ <math display="inline"> ||u|| = \lambda_1(L), ||v|| = \lambda_2(L) </math>.
@@ Line 35: / Line 33: @@
 लैटिस रिडक्शन एल्गोरिदम का उपयोग कई आधुनिक संख्या सैद्धांतिक अनुप्रयोगों में किया जाता है, जिसमें [[स्पिगोट एल्गोरिदम]] की खोज भी शामिल है <math>\pi</math>. यद्यपि सबसे छोटा आधार निर्धारित करना संभवतः एक एनपी-पूर्ण समस्या है, लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिदम जैसे एल्गोरिदम<ref>{{cite journal | author = Lenstra, A. K. | author-link = A. K. Lenstra | author2 = Lenstra, H. W. Jr. | author2-link = H. W. Lenstra Jr. | author3 = Lovász, L. | author3-link = László Lovász | title = परिमेय गुणांकों के साथ बहुपदों का गुणनखंडन| journal = [[Mathematische Annalen]] | volume = 261 | year = 1982 | issue = 4 | pages = 515–534 | hdl = 1887/3810 | doi = 10.1007/BF01457454 | mr = 0682664 | citeseerx = 10.1.1.310.318 | s2cid = 5701340 }}</ref> सबसे खराब स्थिति वाले प्रदर्शन की गारंटी के साथ बहुपद समय में एक छोटा (जरूरी नहीं कि सबसे छोटा) आधार पा सकते हैं। लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिथ्म का व्यापक रूप से [[सार्वजनिक-कुंजी क्रिप्टोग्राफी]] क्रिप्टोसिस्टम के [[क्रिप्ट विश्लेषण]] में उपयोग किया जाता है।
-जब पूर्णांक संबंधों को खोजने के लिए उपयोग किया जाता है, तो एल्गोरिदम के एक विशिष्ट इनपुट में एक संवर्धित होता है <math>n \times n</math> अंतिम कॉलम में प्रविष्टियों के साथ पहचान मैट्रिक्स <math>n</math> तत्व (एक बड़े सकारात्मक स्थिरांक से गुणा किया गया <math>w</math> उन सदिशों को दंडित करना जिनका योग शून्य नहीं है) जिनके बीच संबंध खोजा जाता है।
+जब पूर्णांक संबंधों को खोजने के लिए उपयोग किया जाता है, तो एल्गोरिदम के एक विशिष्ट निविष्ट में एक संवर्धित होता है <math>n \times n</math> अंतिम कॉलम में प्रविष्टियों के साथ पहचान मैट्रिक्स <math>n</math> तत्व (एक बड़े सकारात्मक स्थिरांक से गुणा किया गया <math>w</math> उन सदिशों को दंडित करना जिनका योग शून्य नहीं है) जिनके बीच संबंध खोजा जाता है।
 लगभग-ऑर्थोगोनल आधार की गणना के लिए [[एलएलएल एल्गोरिदम]] का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में [[पूर्णांक प्रोग्रामिंग]] [[पी (जटिलता)]] में की जा सकती है।<ref>{{cite journal|

Anonymous

Search

लैटिस न्यूनन: Difference between revisions

Namespaces

More

Page actions

Revision as of 07:42, 13 July 2023

Contents

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

दो आयामों में