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

Latest revision as of 14:41, 17 October 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$ समानता के साथ वास्तविकता दोष होगा, यदि जब आधार लांबिक हों।

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

दो आयामों में

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

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

    निविष्ट,  $($

@@ Line 1: / Line 1: @@
-[[Image:Lattice-reduction.svg|thumb|right|300px|दो आयामों में जालक में लघूकरण, काले सदिश जालक के लिए दिए गए आधार हैं (नीले बिंदुओं द्वारा दर्शाए गए), लाल सदिश लघुकृत आधार हैं।]]गणित में, '''जालक आधार लघूकरण''' का लक्ष्य, एक पूर्णांक [[जाली (समूह)|जालक]] आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग [[ ओर्थोगोनल |लांबिक]] सदिश वाले [[आधार (रैखिक बीजगणित)|आधार]] का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि  समान्यतः जालक के आयाम में कम से कम घातीय होती है।
+[[Image:Lattice-reduction.svg|thumb|right|300px|दो आयामों में लैटिस में न्यूनन, काले सदिश लैटिस के लिए दिए गए आधार हैं (नीले बिंदुओं द्वारा दर्शाए गए), लाल सदिश लघुकृत आधार हैं।]]गणित में, '''लैटिस आधार न्यूनन''' का लक्ष्य, एक पूर्णांक [[जाली (समूह)|लैटिस]] आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग [[ ओर्थोगोनल |लांबिक]] सदिश वाले [[आधार (रैखिक बीजगणित)|आधार]] का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि  सामान्यतः लैटिस के आयाम में कम से कम घातीय होती है।
 ==लगभग लांबिक==
 लगभग लांबिक की एक माप '<nowiki/>'''लांबिक दोष'''' है। यह आधार सदिश की लंबाई के गुणन की तुलना उनके द्वारा परिभाषित [[समांतर चतुर्भुज]] के आयतन से करता है। पूर्णतः लांबिक आधार वाले सदिश के लिए, ये मात्राएँ समान होंगी।
-<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> के निर्धारक के रूप में जाना जाता है।
 लांबिक दोष, समानांतर चतुर्भुज आयतन द्वारा विभाजित आधार सदिश लंबाई का गुणन है,
@@ Line 11: / Line 11: @@
 ज्यामितीय परिभाषा से यह स्पष्ट होता है कि <math>\delta(B) \ge 1</math> समानता के साथ वास्तविकता दोष होगा, यदि जब आधार लांबिक हों।
-यदि जालक लघूकरण की समस्या को सबसे छोटे संभावित दोष के साथ आधार का पता लगाने के रूप में परिभाषित किया गया है, तो समस्या [[ एनपी कठिन |NP कठिन]] होती है {{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}}।
+यदि लैटिस न्यूनन की समस्या को सबसे छोटे संभावित दोष के साथ आधार का पता लगाने के रूप में परिभाषित किया गया है, तो समस्या [[ एनपी कठिन |NP कठिन]] होती है । हालाँकि, दोष <math>\delta(B) \le c</math> के साथ आधार का पता लगाने के लिए [[बहुपद काल]] कलन विधि मौजूद हैं  जहां c कुछ स्थिरांक है जो केवल आधार सदिश की संख्या और अंतर्निहित समष्टि के आयाम  (यदि भिन्न हो) पर निर्भर करता है। यह कई व्यावहारिक अनुप्रयोगों में एक अच्छा समाधान है।
 ==दो आयामों में==
-केवल दो सदिशों से युक्त आधार के लिए, दो पूर्णांकों के [[सबसे बड़े सामान्य विभाजक के लिए यूक्लिडीयकलनविधि]] के अनुरूप लघूकरण की एक सरल और कुशल विधि है।[[ यूक्लिडियन एल्गोरिथ्म |यूक्लिडीयकलनविधि]] की तरह, विधि पुनरावृत्तीय है, प्रत्येक चरण में छोटे सदिश के पूर्णांक गुणज को जोड़कर या घटाकर दो सदिशों में से बड़े को कम किया जाता है।
+केवल दो सदिशों से युक्त आधार के लिए, दो पूर्णांकों के [[सबसे बड़े सामान्य विभाजक के लिए यूक्लिडीयकलनविधि]] के अनुरूप न्यूनन की एक सरल और कुशल विधि है।[[ यूक्लिडियन एल्गोरिथ्म |यूक्लिडीयकलनविधि]] की तरह, यह तकनीक पुनरावृत्तिशील होती है, प्रत्येक चरण में छोटे सदिश के पूर्णांक गुणज को जोड़कर या घटाकर दो सदिशों में से बड़े को लघुकृत किया जाता है।
-एल्गोरिथ्म का छद्मकोड, जिसे अक्सर लैग्रेंज एल्गोरिदम या लैग्रेंज-गॉस एल्गोरिदम के रूप में जाना जाता है, इस प्रकार है:
+कलन विधि का छद्मकोड, जिसे अक्सर लैग्रेंज कलन विधि या लैग्रेंज-गॉस कलन विधि के रूप में जाना जाता है, वह इस प्रकार है,
-      निविष्ट: <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>.
+      निर्गत, <math display="inline"> ||u|| = \lambda_1(L), ||v|| = \lambda_2(L) </math> के साथ एक आधार <math display="inline"> (u,v) </math>।
       जबकि <math display="inline"> ||v|| < ||u|| </math>:
 <math display="inline"> q := \lfloor {\langle u, \frac{ v}{||v||^2} \rangle } \rceil </math> # निकटतम पूर्णांक तक पूर्णांकित करें
 <math display="inline"> r := u  - qv </math>
            <math display="inline"> u := v </math>
            <math display="inline"> v := r </math>
+अधिक जानकारी के लिए लैग्रेंज के एल्गोरिदम पर अनुभाग देखें। <ref name="Nguyen 2009 pp. 19–69">{{cite book | last=Nguyen | first=Phong Q. | title=The LLL Algorithm | chapter=Hermite’s Constant and Lattice Algorithms | series=Information Security and Cryptography | publisher=Springer Berlin Heidelberg | location=Berlin, Heidelberg | year=2009 | isbn=978-3-642-02294-4 | issn=1619-7100 | doi=10.1007/978-3-642-02295-1_2 | pages=19–69}}</ref>
-<!--- a picture explaining the geometric viewpoint would be great --->
-<ref name= Nguyen 2009 pp. 19–69 > में लैग्रेंज के एल्गोरिदम पर अनुभाग देखें{{cite book | last=Nguyen | first=Phong Q. | title=एलएलएल एल्गोरिदम| chapter=Hermite’s Constant and Lattice Algorithms | series=Information Security and Cryptography | publisher=Springer Berlin Heidelberg | location=Berlin, Heidelberg | year=2009 | isbn=978-3-642-02294-4 | issn=1619-7100 | doi=10.1007/978-3-642-02295-1_2 | pages=19–69}}</ref> अधिक जानकारी के लिए।
 ==अनुप्रयोग==
-लैटिस रिडक्शन एल्गोरिदम का उपयोग कई आधुनिक संख्या सैद्धांतिक अनुप्रयोगों में किया जाता है, जिसमें [[स्पिगोट एल्गोरिदम]] की खोज भी शामिल है <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>\pi</math> के लिए [[स्पिगोट एल्गोरिदम|स्पिगोट कलन विधि]] का आविष्कार भी सम्मिलित है। यद्यपि सबसे छोटे आधार का निर्धारण संभवतः एक NP-पूर्ण समस्या है, लेकिन [[LLL कलन विधि]] जैसे कलन विधि लैटिस सबसे खराब स्थिति के प्रदर्शन की गारंटी के साथ बहुपद <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|
+लगभग-लांबिक आधार की गणना के लिए [[एलएलएल एल्गोरिदम|एलएलएल कलन विधि]] का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में [[पूर्णांक प्रोग्रामिंग|पूर्णांक कार्यरचना]] [[बहुपद समय]] में की जा सकती है।<ref>{{cite journal|
 doi = 10.1287/moor.8.4.538|
 author = Lenstra, H.W.|
@@ Line 47: / Line 45: @@
 citeseerx = 10.1.1.431.5444}}
 </ref>
+==कलन विधि==
+निम्नलिखित कलन विधि लैटिस आधारों को लघुकृत करते हैं, इन कलन विधि के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं।
-==एल्गोरिदम==
-निम्नलिखित एल्गोरिदम जालक आधारों को कम करते हैं; इन एल्गोरिदम के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं।
 {|
 |-
-! Year
+! वर्ष
-! Algorithm
+! कलन विधि
-! Implementation
+! कार्यान्वयन
 |-
 | 1773
-| Lagrange/Gauss reduction for 2D lattices
+| 2D लैटिस के लिए लैग्रेंज/गॉस न्यूनन
 |
 |-
 | 1982
-| [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|Lenstra–Lenstra–Lovász]] reduction
+| [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|लेनस्ट्रा-लेनस्ट्रा-लोवेज़]] न्यूनन
 | [[Number Theory Library|NTL]], [https://github.com/dstehle/fplll fplll]
 |-
 | 1987
-| Block [[Korkine–Zolotarev lattice basis reduction algorithm|Korkine–Zolotarev]]<ref>{{cite arXiv|last1=Hanrot|first1=Guillaume|last2=Stehlé|first2=Damien|title=Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases|date=2008|eprint=0801.3331|class=math.NT}}</ref>
+| ब्लॉक [[Korkine–Zolotarev lattice basis reduction algorithm|कॉर्किन-ज़ोलोटारेव]]
+<ref>{{cite arXiv|last1=Hanrot|first1=Guillaume|last2=Stehlé|first2=Damien|title=Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases|date=2008|eprint=0801.3331|class=math.NT}}</ref>
 | [[Number Theory Library|NTL]], [https://github.com/dstehle/fplll fplll]
 |-
 | 1993
-| Seysen Reduction<ref>{{cite journal |last1=Seysen |first1=Martin |title=Simultaneous reduction of a lattice basis and its reciprocal basis |journal=Combinatorica |date=September 1993 |volume=13 |issue=3 |pages=363–376 |doi=10.1007/BF01202355 |s2cid=206791637 }}</ref>
+| सीसेन न्यूनन<ref>{{cite journal |last1=Seysen |first1=Martin |title=Simultaneous reduction of a lattice basis and its reciprocal basis |journal=Combinatorica |date=September 1993 |volume=13 |issue=3 |pages=363–376 |doi=10.1007/BF01202355 |s2cid=206791637 }}</ref>
 |  [https://github.com/christianpeel/LLLplus.jl/blob/master/src/seysen.jl LLLplus]
 |}
@@ Line 78: / Line 75: @@
 ==संदर्भ==
 {{Reflist}}
-[[Category: क्रिप्टोग्राफी का सिद्धांत]] [[Category: कम्प्यूटेशनल संख्या सिद्धांत]] [[Category: जाली बिंदु]] [[Category: लीनियर अलजेब्रा]] [[Category: जाली-आधारित क्रिप्टोग्राफी]] [[Category: पोस्ट-क्वांटम क्रिप्टोग्राफी]]
-[[Category: Machine Translated Page]]
+[[Category:All articles with unsourced statements]]
+[[Category:Articles with invalid date parameter in template]]
+[[Category:Articles with unsourced statements from July 2022]]
 [[Category:Created On 07/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with reference errors]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:कम्प्यूटेशनल संख्या सिद्धांत]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 14:41, 17 October 2023

Contents

लगभग लांबिक

दो आयामों में