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

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

यदि जालक लघूकरण की समस्या को सबसे छोटे संभावित दोष के साथ आधार का पता लगाने के रूप में परिभाषित किया गया है, तो समस्या NP कठिन होती है^{[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)}$ .

    जबकि  ${\textstyle ||v||<||u||}$ :

${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$ # निकटतम पूर्णांक तक पूर्णांकित करें ${\textstyle r:=u-qv}$

          ${\textstyle u:=v}$ 
          ${\textstyle v:=r}$

Cite error: Invalid <ref> tag; invalid names, e.g. too many अधिक जानकारी के लिए।

अनुप्रयोग

लैटिस रिडक्शन एल्गोरिदम का उपयोग कई आधुनिक संख्या सैद्धांतिक अनुप्रयोगों में किया जाता है, जिसमें स्पिगोट एल्गोरिदम की खोज भी शामिल है $\pi$ . यद्यपि सबसे छोटा आधार निर्धारित करना संभवतः एक एनपी-पूर्ण समस्या है, लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिदम जैसे एल्गोरिदम^[1] सबसे खराब स्थिति वाले प्रदर्शन की गारंटी के साथ बहुपद समय में एक छोटा (जरूरी नहीं कि सबसे छोटा) आधार पा सकते हैं। लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिथ्म का व्यापक रूप से सार्वजनिक-कुंजी क्रिप्टोग्राफी क्रिप्टोसिस्टम के क्रिप्ट विश्लेषण में उपयोग किया जाता है।

जब पूर्णांक संबंधों को खोजने के लिए उपयोग किया जाता है, तो एल्गोरिदम के एक विशिष्ट निविष्ट में एक संवर्धित होता है $n\times n$ अंतिम कॉलम में प्रविष्टियों के साथ पहचान आव्यूह $n$ तत्व (एक बड़े सकारात्मक स्थिरांक से गुणा किया गया $w$ उन सदिशों को दंडित करना जिनका योग शून्य नहीं है) जिनके बीच संबंध खोजा जाता है।

लगभग-लांबिक आधार की गणना के लिए एलएलएल एल्गोरिदम का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में पूर्णांक प्रोग्रामिंग पी (जटिलता) में की जा सकती है।^[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.

[1] 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.

[2] 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.

[3] Hanrot, Guillaume; Stehlé, Damien (2008). "Worst-Case Hermite-Korkine-Zolotarev Reduced Lattice Bases". arXiv:0801.3331 [math.NT].

[4] 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.

[1]

[2]

[3]

[4]

@@ Line 9: / Line 9: @@
 :<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|date=July 2022}}. कई व्यावहारिक अनुप्रयोगों में यह एक अच्छा समाधान है{{Citation needed|date=July 2022}}.
+यदि जालक लघूकरण की समस्या को सबसे छोटे संभावित दोष के साथ आधार का पता लगाने के रूप में परिभाषित किया गया है, तो समस्या [[ एनपी कठिन |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}}.
 ==दो आयामों में==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 08:37, 13 July 2023

Contents

लगभग लांबिक

दो आयामों में

अनुप्रयोग

एल्गोरिदम

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 08:37, 13 July 2023

लगभग लांबिक

दो आयामों में

अनुप्रयोग

एल्गोरिदम

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories