लैटिस न्यूनन: Difference between revisions
From Vigyanwiki
No edit summary |
|||
| (25 intermediate revisions by 5 users not shown) | |||
| 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>\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) = \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> समानता के साथ वास्तविकता दोष होगा, यदि जब आधार लांबिक हों। | ||
यदि | यदि लैटिस न्यूनन की समस्या को सबसे छोटे संभावित दोष के साथ आधार का पता लगाने के रूप में परिभाषित किया गया है, तो समस्या [[ एनपी कठिन |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|| = \lambda_1(L), ||v|| = \lambda_2(L) </math> के साथ एक आधार <math display="inline"> (u,v) </math>। | |||
जबकि <math display="inline"> ||v|| < ||u|| </math>: | जबकि <math display="inline"> ||v|| < ||u|| </math>: | ||
<math display="inline"> q := \lfloor {\langle u, \frac{ v}{||v||^2} \rangle } \rceil </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"> r := u - qv </math> | ||
<math display="inline"> u := v </math> | <math display="inline"> u := v </math> | ||
<math display="inline"> v := r </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> | |||
<ref name= Nguyen 2009 pp. 19–69 > | |||
==अनुप्रयोग== | ==अनुप्रयोग== | ||
लैटिस | लैटिस न्यूनन कलन विधि का उपयोग कई आधुनिक संख्या सैद्धांतिक अनुप्रयोगों में किया जाता है, जिसमें <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> से गुणा किया जाता है जिनका योग शून्य नहीं होता है) होते हैं जिनके बीच संबंध का पता लगाया जाता है। | ||
लगभग- | लगभग-लांबिक आधार की गणना के लिए [[एलएलएल एल्गोरिदम|एलएलएल कलन विधि]] का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में [[पूर्णांक प्रोग्रामिंग|पूर्णांक कार्यरचना]] [[बहुपद समय]] में की जा सकती है।<ref>{{cite journal| | ||
doi = 10.1287/moor.8.4.538| | doi = 10.1287/moor.8.4.538| | ||
author = Lenstra, H.W.| | author = Lenstra, H.W.| | ||
| Line 47: | Line 45: | ||
citeseerx = 10.1.1.431.5444}} | citeseerx = 10.1.1.431.5444}} | ||
</ref> | </ref> | ||
==कलन विधि== | |||
निम्नलिखित कलन विधि लैटिस आधारों को लघुकृत करते हैं, इन कलन विधि के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं। | |||
== | |||
निम्नलिखित | |||
{| | {| | ||
|- | |- | ||
! | ! वर्ष | ||
! | ! कलन विधि | ||
! | ! कार्यान्वयन | ||
|- | |- | ||
| 1773 | | 1773 | ||
| | | 2D लैटिस के लिए लैग्रेंज/गॉस न्यूनन | ||
| | | | ||
|- | |- | ||
| 1982 | | 1982 | ||
| [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm| | | [[Lenstra–Lenstra–Lovász lattice basis reduction algorithm|लेनस्ट्रा-लेनस्ट्रा-लोवेज़]] न्यूनन | ||
| [[Number Theory Library|NTL]], [https://github.com/dstehle/fplll fplll] | | [[Number Theory Library|NTL]], [https://github.com/dstehle/fplll fplll] | ||
|- | |- | ||
| 1987 | | 1987 | ||
| | | ब्लॉक [[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] | | [[Number Theory Library|NTL]], [https://github.com/dstehle/fplll fplll] | ||
|- | |- | ||
| 1993 | | 1993 | ||
| | | सीसेन न्यूनन<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] | | [https://github.com/christianpeel/LLLplus.jl/blob/master/src/seysen.jl LLLplus] | ||
|} | |} | ||
| Line 78: | Line 75: | ||
==संदर्भ== | ==संदर्भ== | ||
{{Reflist}} | {{Reflist}} | ||
[[Category: | [[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:Created On 07/07/2023]] | ||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with reference errors]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:कम्प्यूटेशनल संख्या सिद्धांत]] | |||
Latest revision as of 14:41, 17 October 2023
गणित में, लैटिस आधार न्यूनन का लक्ष्य, एक पूर्णांक लैटिस आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग लांबिक सदिश वाले आधार का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि सामान्यतः लैटिस के आयाम में कम से कम घातीय होती है।
लगभग लांबिक
लगभग लांबिक की एक माप 'लांबिक दोष' है। यह आधार सदिश की लंबाई के गुणन की तुलना उनके द्वारा परिभाषित समांतर चतुर्भुज के आयतन से करता है। पूर्णतः लांबिक आधार वाले सदिश के लिए, ये मात्राएँ समान होंगी।
सदिशों के किसी विशेष आधार को आव्यूह , द्वारा दर्शाया जा सकता है, जिसके स्तंभ आधार सदिश हैं। पूर्ण आयामी स्थिति में जहां आधार सदिश की संख्या उनके द्वारा व्याप्त समष्टि के आयाम के बराबर होती है, यह आव्यूह वर्गाकार होता है, और मूल समांतर चतुर्भुज का आयतन इस आव्यूह के निर्धारक का पूर्ण मान होता है। यदि सदिशों की संख्या अंतर्निहित समष्टि के आयाम से कम है, तो आयतन है।किसी दिए गए लैटिस के लिए , यह आयतन किसी भी पर समान (संकेत तक) है, और इसलिए इसे लैटिस या लैटिस स्थिरांक के निर्धारक के रूप में जाना जाता है।
लांबिक दोष, समानांतर चतुर्भुज आयतन द्वारा विभाजित आधार सदिश लंबाई का गुणन है,
ज्यामितीय परिभाषा से यह स्पष्ट होता है कि समानता के साथ वास्तविकता दोष होगा, यदि जब आधार लांबिक हों।
यदि लैटिस न्यूनन की समस्या को सबसे छोटे संभावित दोष के साथ आधार का पता लगाने के रूप में परिभाषित किया गया है, तो समस्या NP कठिन होती है । हालाँकि, दोष के साथ आधार का पता लगाने के लिए बहुपद काल कलन विधि मौजूद हैं जहां c कुछ स्थिरांक है जो केवल आधार सदिश की संख्या और अंतर्निहित समष्टि के आयाम (यदि भिन्न हो) पर निर्भर करता है। यह कई व्यावहारिक अनुप्रयोगों में एक अच्छा समाधान है।
दो आयामों में
केवल दो सदिशों से युक्त आधार के लिए, दो पूर्णांकों के सबसे बड़े सामान्य विभाजक के लिए यूक्लिडीयकलनविधि के अनुरूप न्यूनन की एक सरल और कुशल विधि है।यूक्लिडीयकलनविधि की तरह, यह तकनीक पुनरावृत्तिशील होती है, प्रत्येक चरण में छोटे सदिश के पूर्णांक गुणज को जोड़कर या घटाकर दो सदिशों में से बड़े को लघुकृत किया जाता है।
कलन विधि का छद्मकोड, जिसे अक्सर लैग्रेंज कलन विधि या लैग्रेंज-गॉस कलन विधि के रूप में जाना जाता है, वह इस प्रकार है,
निविष्ट, लैटिस के लिए एक आधार । मान लीजिए कि , अन्यथा उन्हें एक-दूसरे के साथ बदल दें। निर्गत, के साथ एक आधार ।
जबकि :
# निकटतम पूर्णांक तक पूर्णांकित करें
अधिक जानकारी के लिए लैग्रेंज के एल्गोरिदम पर अनुभाग देखें। [1]
अनुप्रयोग
लैटिस न्यूनन कलन विधि का उपयोग कई आधुनिक संख्या सैद्धांतिक अनुप्रयोगों में किया जाता है, जिसमें के लिए स्पिगोट कलन विधि का आविष्कार भी सम्मिलित है। यद्यपि सबसे छोटे आधार का निर्धारण संभवतः एक NP-पूर्ण समस्या है, लेकिन LLL कलन विधि जैसे कलन विधि लैटिस सबसे खराब स्थिति के प्रदर्शन की गारंटी के साथ बहुपद [2] समय में एक छोटा (जरूरी नहीं कि सबसे छोटा) आधार प्राप्त कर सकते हैं। लेनस्ट्रा-लेनस्ट्रा-लोवेज़ लैटिस आधार न्यूनन एल्गोरिथ्म का व्यापक रूप से सार्वजनिक-कुंजी क्रिप्टोग्राफी क्रिप्टोसिस्टम के क्रिप्ट विश्लेषण में उपयोग किया जाता है।
जब पूर्णांक संबंधों को प्रतिलब्धि करने के लिए उपयोग किया जाता है, तो कलन विधि के एक विशिष्ट निविष्ट में अंतिम स्तम्भ में प्रविष्टियों के साथ एक संवर्धित तत्समक आव्यूह होता है जिसमें तत्व (उन सदिशो को दंडित करने के लिए एक बड़े सकारात्मक स्थिरांक से गुणा किया जाता है जिनका योग शून्य नहीं होता है) होते हैं जिनके बीच संबंध का पता लगाया जाता है।
लगभग-लांबिक आधार की गणना के लिए एलएलएल कलन विधि का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में पूर्णांक कार्यरचना बहुपद समय में की जा सकती है।[3]
कलन विधि
निम्नलिखित कलन विधि लैटिस आधारों को लघुकृत करते हैं, इन कलन विधि के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं।
| वर्ष | कलन विधि | कार्यान्वयन |
|---|---|---|
| 1773 | 2D लैटिस के लिए लैग्रेंज/गॉस न्यूनन | |
| 1982 | लेनस्ट्रा-लेनस्ट्रा-लोवेज़ न्यूनन | NTL, fplll |
| 1987 | ब्लॉक कॉर्किन-ज़ोलोटारेव | NTL, fplll |
| 1993 | सीसेन न्यूनन[5] | LLLplus |
संदर्भ
- ↑ Nguyen, Phong Q. (2009). "Hermite's Constant and Lattice Algorithms". The LLL Algorithm. Information Security and Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 19–69. doi:10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4. ISSN 1619-7100.
- ↑ Lenstra, A. K.; Lenstra, H. W. Jr.; Lovász, L. (1982). "परिमेय गुणांकों के साथ बहुपदों का गुणनखंडन". Mathematische Annalen. 261 (4): 515–534. CiteSeerX 10.1.1.310.318. doi:10.1007/BF01457454. hdl:1887/3810. MR 0682664. S2CID 5701340.
- ↑ Lenstra, H.W. (1983). "Integer programming with a fixed number of variables". Math. Oper. Res. 8 (4): 538–548. CiteSeerX 10.1.1.431.5444. doi:10.1287/moor.8.4.538.
- ↑ Hanrot, Guillaume; Stehlé, Damien (2008). "Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases". arXiv:0801.3331 [math.NT].
- ↑ Seysen, Martin (September 1993). "Simultaneous reduction of a lattice basis and its reciprocal basis". Combinatorica. 13 (3): 363–376. doi:10.1007/BF01202355. S2CID 206791637.
