लैटिस न्यूनन: Difference between revisions
m (Abhishek moved page जाली में कमी to लैटिस न्यूनन without leaving a redirect) |
No edit summary |
||
| Line 1: | Line 1: | ||
[[Image:Lattice-reduction.svg|thumb|right|300px|दो आयामों में | [[Image:Lattice-reduction.svg|thumb|right|300px|दो आयामों में लैटिस में न्यूनन, काले सदिश लैटिस के लिए दिए गए आधार हैं (नीले बिंदुओं द्वारा दर्शाए गए), लाल सदिश लघुकृत आधार हैं।]]गणित में, '''लैटिस आधार न्यूनन''' का लक्ष्य, एक पूर्णांक [[जाली (समूह)|लैटिस]] आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग [[ ओर्थोगोनल |लांबिक]] सदिश वाले [[आधार (रैखिक बीजगणित)|आधार]] का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि समान्यतः लैटिस के आयाम में कम से कम घातीय होती है। | ||
==लगभग लांबिक== | ==लगभग लांबिक== | ||
लगभग लांबिक की एक माप '<nowiki/>'''लांबिक दोष'''' है। यह आधार सदिश की लंबाई के गुणन की तुलना उनके द्वारा परिभाषित [[समांतर चतुर्भुज]] के आयतन से करता है। पूर्णतः लांबिक आधार वाले सदिश के लिए, ये मात्राएँ समान होंगी। | लगभग लांबिक की एक माप '<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>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> समानता के साथ वास्तविकता दोष होगा, यदि जब आधार लांबिक हों। | ज्यामितीय परिभाषा से यह स्पष्ट होता है कि <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}}। | ||
==दो आयामों में== | ==दो आयामों में== | ||
केवल दो सदिशों से युक्त आधार के लिए, दो पूर्णांकों के [[सबसे बड़े सामान्य विभाजक के लिए यूक्लिडीयकलनविधि]] के अनुरूप | केवल दो सदिशों से युक्त आधार के लिए, दो पूर्णांकों के [[सबसे बड़े सामान्य विभाजक के लिए यूक्लिडीयकलनविधि]] के अनुरूप न्यूनन की एक सरल और कुशल विधि है।[[ यूक्लिडियन एल्गोरिथ्म |यूक्लिडीयकलनविधि]] की तरह, यह तकनीक पुनरावृत्तिशील होती है, प्रत्येक चरण में छोटे सदिश के पूर्णांक गुणज को जोड़कर या घटाकर दो सदिशों में से बड़े को लघुकृत किया जाता है। | ||
कलन विधि का छद्मकोड, जिसे अक्सर लैग्रेंज कलन विधि या लैग्रेंज-गॉस कलन विधि के रूप में जाना जाता है, वह इस प्रकार है, | कलन विधि का छद्मकोड, जिसे अक्सर लैग्रेंज कलन विधि या लैग्रेंज-गॉस कलन विधि के रूप में जाना जाता है, वह इस प्रकार है, | ||
निविष्ट, <math display="inline"> (u,v) </math> | निविष्ट, <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"> ||u|| = \lambda_1(L), ||v|| = \lambda_2(L) </math> के साथ एक आधार <math display="inline"> (u,v) </math>। | ||
| Line 30: | Line 30: | ||
==अनुप्रयोग== | ==अनुप्रयोग== | ||
लैटिस न्यूनन कलन विधि का उपयोग कई आधुनिक संख्या सैद्धांतिक अनुप्रयोगों में किया जाता है, जिसमें <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> से गुणा किया जाता है जिनका योग शून्य नहीं होता है) होते हैं जिनके बीच संबंध का पता लगाया जाता है। | ||
| Line 47: | Line 47: | ||
</ref> | </ref> | ||
==कलन विधि== | ==कलन विधि== | ||
निम्नलिखित कलन विधि | निम्नलिखित कलन विधि लैटिस आधारों को लघुकृत करते हैं, इन कलन विधि के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं। | ||
{| | {| | ||
| Line 56: | Line 56: | ||
|- | |- | ||
| 1773 | | 1773 | ||
| 2D | | 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] | ||
|- | |- | ||
| Line 69: | Line 69: | ||
|- | |- | ||
| 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] | ||
|} | |} | ||
Revision as of 14:43, 14 July 2023
गणित में, लैटिस आधार न्यूनन का लक्ष्य, एक पूर्णांक लैटिस आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग लांबिक सदिश वाले आधार का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि समान्यतः लैटिस के आयाम में कम से कम घातीय होती है।
लगभग लांबिक
लगभग लांबिक की एक माप 'लांबिक दोष' है। यह आधार सदिश की लंबाई के गुणन की तुलना उनके द्वारा परिभाषित समांतर चतुर्भुज के आयतन से करता है। पूर्णतः लांबिक आधार वाले सदिश के लिए, ये मात्राएँ समान होंगी।
सदिशों के किसी विशेष आधार को आव्यूह , द्वारा दर्शाया जा सकता है, जिसके स्तंभ आधार सदिश हैं। पूर्ण आयामी स्थिति में जहां आधार सदिश की संख्या उनके द्वारा व्याप्त समष्टि के आयाम के बराबर होती है, यह आव्यूह वर्गाकार होता है, और मूल समांतर चतुर्भुज का आयतन इस आव्यूह के निर्धारक का पूर्ण मान होता है। यदि सदिशों की संख्या अंतर्निहित समष्टि के आयाम से कम है, तो आयतन है।किसी दिए गए लैटिस के लिए , यह आयतन किसी भी पर समान (संकेत तक) है, और इसलिए इसे लैटिस या लैटिस स्थिरांक के निर्धारक के रूप में जाना जाता है।
लांबिक दोष, समानांतर चतुर्भुज आयतन द्वारा विभाजित आधार सदिश लंबाई का गुणन है,
ज्यामितीय परिभाषा से यह स्पष्ट होता है कि समानता के साथ वास्तविकता दोष होगा, यदि जब आधार लांबिक हों।
यदि लैटिस न्यूनन की समस्या को सबसे छोटे संभावित दोष के साथ आधार का पता लगाने के रूप में परिभाषित किया गया है, तो समस्या NP कठिन होती है[citation needed]। हालाँकि, दोष के साथ आधार का पता लगाने के लिए बहुपद काल कलन विधि मौजूद हैं जहां c कुछ स्थिरांक है जो केवल आधार सदिश की संख्या और अंतर्निहित समष्टि के आयाम (यदि भिन्न हो) पर निर्भर करता है[citation needed]। यह कई व्यावहारिक अनुप्रयोगों में एक अच्छा समाधान है[citation needed]।
दो आयामों में
केवल दो सदिशों से युक्त आधार के लिए, दो पूर्णांकों के सबसे बड़े सामान्य विभाजक के लिए यूक्लिडीयकलनविधि के अनुरूप न्यूनन की एक सरल और कुशल विधि है।यूक्लिडीयकलनविधि की तरह, यह तकनीक पुनरावृत्तिशील होती है, प्रत्येक चरण में छोटे सदिश के पूर्णांक गुणज को जोड़कर या घटाकर दो सदिशों में से बड़े को लघुकृत किया जाता है।
कलन विधि का छद्मकोड, जिसे अक्सर लैग्रेंज कलन विधि या लैग्रेंज-गॉस कलन विधि के रूप में जाना जाता है, वह इस प्रकार है,
निविष्ट, लैटिस के लिए एक आधार । मान लीजिए कि , अन्यथा उन्हें एक-दूसरे के साथ बदल दें। निर्गत, के साथ एक आधार ।
जबकि :
# निकटतम पूर्णांक तक पूर्णांकित करें
अधिक जानकारी के लिएCite error: Invalid <ref> tag; invalid names, e.g. too many लैग्रेंज के कलन विधि पर अनुभाग देखें।
अनुप्रयोग
लैटिस न्यूनन कलन विधि का उपयोग कई आधुनिक संख्या सैद्धांतिक अनुप्रयोगों में किया जाता है, जिसमें के लिए स्पिगोट कलन विधि का आविष्कार भी सम्मिलित है। यद्यपि सबसे छोटे आधार का निर्धारण संभवतः एक NP-पूर्ण समस्या है, लेकिन LLL कलन विधि जैसे कलन विधि लैटिस सबसे खराब स्थिति के प्रदर्शन की गारंटी के साथ बहुपद [1] समय में एक छोटा (जरूरी नहीं कि सबसे छोटा) आधार प्राप्त कर सकते हैं। लेनस्ट्रा-लेनस्ट्रा-लोवेज़ लैटिस आधार न्यूनन एल्गोरिथ्म का व्यापक रूप से सार्वजनिक-कुंजी क्रिप्टोग्राफी क्रिप्टोसिस्टम के क्रिप्ट विश्लेषण में उपयोग किया जाता है।
जब पूर्णांक संबंधों को प्रतिलब्धि करने के लिए उपयोग किया जाता है, तो कलन विधि के एक विशिष्ट निविष्ट में अंतिम स्तम्भ में प्रविष्टियों के साथ एक संवर्धित तत्समक आव्यूह होता है जिसमें तत्व (उन सदिशो को दंडित करने के लिए एक बड़े सकारात्मक स्थिरांक से गुणा किया जाता है जिनका योग शून्य नहीं होता है) होते हैं जिनके बीच संबंध का पता लगाया जाता है।
लगभग-लांबिक आधार की गणना के लिए एलएलएल कलन विधि का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में पूर्णांक कार्यरचना बहुपद समय में की जा सकती है।[2]
कलन विधि
निम्नलिखित कलन विधि लैटिस आधारों को लघुकृत करते हैं, इन कलन विधि के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं।
| वर्ष | कलन विधि | कार्यान्वयन |
|---|---|---|
| 1773 | 2D लैटिस के लिए लैग्रेंज/गॉस न्यूनन | |
| 1982 | लेनस्ट्रा-लेनस्ट्रा-लोवेज़ न्यूनन | NTL, fplll |
| 1987 | ब्लॉक कॉर्किन-ज़ोलोटारेव | NTL, fplll |
| 1993 | सीसेन न्यूनन[4] | LLLplus |
संदर्भ
- ↑ 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.
