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

Revision as of 10:41, 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||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$  के साथ एक आधार  ${\textstyle (u,v)}$ ।

    जबकि  ${\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$ के लिए स्पिगोट कलन विधि का आविष्कार भी सम्मिलित है। यद्यपि सबसे छोटा आधार निर्धारित करना संभवतः एक एनपी-पूर्ण समस्या है, LLL कलन विधि जैसे कलन विधि जालक आधार लघूकरण कलन विधि जैसे कलन विधि^[1] सबसे खराब स्थिति वाले प्रदर्शन की गारंटी के साथ बहुपद समय में एक छोटा (जरूरी नहीं कि सबसे छोटा) आधार पा सकते हैं। लेनस्ट्रा-लेनस्ट्रा-लोवेज़ जालक आधार लघूकरण एल्गोरिथ्म का व्यापक रूप से सार्वजनिक-कुंजी क्रिप्टोग्राफी क्रिप्टोसिस्टम के क्रिप्ट विश्लेषण में उपयोग किया जाता है।

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

लगभग-लांबिक आधार की गणना के लिए एलएलएल कलन विधि का उपयोग यह दिखाने के लिए किया गया था कि किसी भी निश्चित आयाम में पूर्णांक कार्यरचना बहुपद समय में की जा सकती है।^[2]

कलन विधि

निम्नलिखित कलन विधि जालक आधारों को लघुकृत करते हैं, इन कलन विधि के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं।

वर्ष	कलन विधि	कार्यान्वयन
1773	2D जालक के लिए लैग्रेंज/गॉस लघूकरण
1982	लेनस्ट्रा-लेनस्ट्रा-लोवेज़ लघूकरण	NTL, fplll
1987	ब्लॉक कॉर्किन-ज़ोलोटारेव ^[3]	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.

[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 34: / Line 34: @@
 जब पूर्णांक संबंधों को खोजने के लिए उपयोग किया जाता है, तो कलन विधि के एक विशिष्ट निविष्ट में एक संवर्धित होता है <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 49: / Line 49: @@
 ==कलन विधि==
-निम्नलिखित कलन विधि जालक आधारों को कम करते हैं; इन कलन विधि के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं।
+निम्नलिखित कलन विधि जालक आधारों को लघुकृत करते हैं, इन कलन विधि के कई सार्वजनिक कार्यान्वयन भी सूचीबद्ध हैं।
 {|
 |-
-! 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]
 |}

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 10:41, 13 July 2023

Contents

लगभग लांबिक

दो आयामों में

अनुप्रयोग

कलन विधि

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 10:41, 13 July 2023

लगभग लांबिक

दो आयामों में

अनुप्रयोग

कलन विधि

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories