लैटिस न्यूनन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[Image:Lattice-reduction.svg|thumb|right|300px|दो आयामों में जालक में | [[Image:Lattice-reduction.svg|thumb|right|300px|दो आयामों में जालक में लघूकरण, काले सदिश जालक के लिए दिए गए आधार हैं (नीले बिंदुओं द्वारा दर्शाए गए), लाल सदिश लघुकृत आधार हैं।]]गणित में, '''जालक आधार लघूकरण''' का लक्ष्य, एक पूर्णांक [[जाली (समूह)|जालक]] आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग [[ ओर्थोगोनल |लांबिक]] सदिश वाले [[आधार (रैखिक बीजगणित)|आधार]] का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि समान्यतः जालक के आयाम में कम से कम घातीय होती है। | ||
==लगभग ऑर्थोगोनल== | ==लगभग ऑर्थोगोनल== | ||
लगभग ऑर्थोगोनल का एक माप 'ऑर्थोगोनैलिटी दोष' है। यह आधार | लगभग ऑर्थोगोनल का एक माप 'ऑर्थोगोनैलिटी दोष' है। यह आधार सदिश की लंबाई के उत्पाद की तुलना उनके द्वारा परिभाषित समांतर चतुर्भुज के आयतन से करता है। पूर्णतः ऑर्थोगोनल आधार वाले सदिश के लिए, ये मात्राएँ समान होंगी। | ||
का कोई विशेष आधार <math>n</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) = \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> समानता के साथ यदि और केवल यदि आधार ऑर्थोगोनल है। | ज्यामितीय परिभाषा से इसकी सराहना की जा सकती है <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|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"> ||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>. | ||
| 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>\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> उन सदिशों को दंडित करना जिनका योग शून्य नहीं है) जिनके बीच संबंध खोजा जाता है। | ||
लगभग-ऑर्थोगोनल आधार की गणना के लिए [[एलएलएल एल्गोरिदम]] का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में [[पूर्णांक प्रोग्रामिंग]] [[पी (जटिलता)]] में की जा सकती है।<ref>{{cite journal| | लगभग-ऑर्थोगोनल आधार की गणना के लिए [[एलएलएल एल्गोरिदम]] का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में [[पूर्णांक प्रोग्रामिंग]] [[पी (जटिलता)]] में की जा सकती है।<ref>{{cite journal| | ||
Revision as of 07:42, 13 July 2023
गणित में, जालक आधार लघूकरण का लक्ष्य, एक पूर्णांक जालक आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग लांबिक सदिश वाले आधार का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि समान्यतः जालक के आयाम में कम से कम घातीय होती है।
लगभग ऑर्थोगोनल
लगभग ऑर्थोगोनल का एक माप 'ऑर्थोगोनैलिटी दोष' है। यह आधार सदिश की लंबाई के उत्पाद की तुलना उनके द्वारा परिभाषित समांतर चतुर्भुज के आयतन से करता है। पूर्णतः ऑर्थोगोनल आधार वाले सदिश के लिए, ये मात्राएँ समान होंगी।
का कोई विशेष आधार सदिश को मैट्रिक्स द्वारा दर्शाया जा सकता है (गणित) , जिनके कॉलम आधार सदिश हैं . पूर्ण आयामी मामले में जहां आधार सदिश की संख्या उनके द्वारा व्याप्त स्थान के आयाम के बराबर होती है, यह मैट्रिक्स वर्गाकार होता है, और मौलिक समांतर चतुर्भुज का आयतन इस मैट्रिक्स के निर्धारक का पूर्ण मान होता है . यदि सदिशों की संख्या अंतर्निहित स्थान के आयाम से कम है, तो आयतन है . किसी दिए गए जालक के लिए , यह आयतन किसी भी आधार के लिए समान (हस्ताक्षर तक) है, और इसलिए इसे जालक के निर्धारक के रूप में जाना जाता है या जालक स्थिरांक .
ऑर्थोगोनैलिटी दोष, समानांतर चतुर्भुज आयतन द्वारा विभाजित आधार सदिश लंबाई का उत्पाद है;
ज्यामितीय परिभाषा से इसकी सराहना की जा सकती है समानता के साथ यदि और केवल यदि आधार ऑर्थोगोनल है।
यदि जालक कमी की समस्या को सबसे छोटे संभावित दोष के साथ आधार खोजने के रूप में परिभाषित किया गया है, तो समस्या एनपी कठिन है[citation needed]. हालाँकि, दोष के साथ आधार खोजने के लिए बहुपद समय एल्गोरिदम मौजूद हैं जहां c कुछ स्थिरांक है जो केवल आधार सदिश की संख्या और अंतर्निहित स्थान के आयाम पर निर्भर करता है (यदि भिन्न हो)[citation needed]. कई व्यावहारिक अनुप्रयोगों में यह एक अच्छा समाधान है[citation needed].
दो आयामों में
केवल दो सदिशों से युक्त आधार के लिए, दो पूर्णांकों के सबसे बड़े सामान्य विभाजक के लिए यूक्लिडियन एल्गोरिदम के अनुरूप लघूकरण की एक सरल और कुशल विधि है। यूक्लिडियन एल्गोरिथ्म की तरह, विधि पुनरावृत्तीय है; प्रत्येक चरण में छोटे सदिश के पूर्णांक गुणज को जोड़कर या घटाकर दो सदिशों में से बड़े को कम किया जाता है।
एल्गोरिथ्म का छद्मकोड, जिसे अक्सर लैग्रेंज एल्गोरिदम या लैग्रेंज-गॉस एल्गोरिदम के रूप में जाना जाता है, इस प्रकार है:
निविष्ट: जालक के लिए एक आधार . ये मान लीजिए , अन्यथा उन्हें स्वैप करें। आउटपुट: एक आधार साथ .
जबकि :
# निकटतम पूर्णांक तक पूर्णांकित करें
Cite error: Invalid <ref> tag; invalid names, e.g. too many अधिक जानकारी के लिए।
अनुप्रयोग
लैटिस रिडक्शन एल्गोरिदम का उपयोग कई आधुनिक संख्या सैद्धांतिक अनुप्रयोगों में किया जाता है, जिसमें स्पिगोट एल्गोरिदम की खोज भी शामिल है . यद्यपि सबसे छोटा आधार निर्धारित करना संभवतः एक एनपी-पूर्ण समस्या है, लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिदम जैसे एल्गोरिदम[1] सबसे खराब स्थिति वाले प्रदर्शन की गारंटी के साथ बहुपद समय में एक छोटा (जरूरी नहीं कि सबसे छोटा) आधार पा सकते हैं। लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिथ्म का व्यापक रूप से सार्वजनिक-कुंजी क्रिप्टोग्राफी क्रिप्टोसिस्टम के क्रिप्ट विश्लेषण में उपयोग किया जाता है।
जब पूर्णांक संबंधों को खोजने के लिए उपयोग किया जाता है, तो एल्गोरिदम के एक विशिष्ट निविष्ट में एक संवर्धित होता है अंतिम कॉलम में प्रविष्टियों के साथ पहचान मैट्रिक्स तत्व (एक बड़े सकारात्मक स्थिरांक से गुणा किया गया उन सदिशों को दंडित करना जिनका योग शून्य नहीं है) जिनके बीच संबंध खोजा जाता है।
लगभग-ऑर्थोगोनल आधार की गणना के लिए एलएलएल एल्गोरिदम का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में पूर्णांक प्रोग्रामिंग पी (जटिलता) में की जा सकती है।[2]
एल्गोरिदम
निम्नलिखित एल्गोरिदम जालक आधारों को कम करते हैं; इन एल्गोरिदम के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं।
| Year | Algorithm | Implementation |
|---|---|---|
| 1773 | Lagrange/Gauss reduction for 2D lattices | |
| 1982 | Lenstra–Lenstra–Lovász reduction | NTL, fplll |
| 1987 | Block Korkine–Zolotarev[3] | NTL, fplll |
| 1993 | Seysen Reduction[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.
