लेनस्ट्रा-लेनस्ट्रा-लोवाज़ जाली आधार कमी एल्गोरिथ्म: Difference between revisions

From Vigyanwiki
No edit summary
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Algorithm in computational number theory}}
{{Short description|Algorithm in computational number theory}}
{{Use dmy dates|date=July 2022}}
 
लेनस्ट्रा-लेनस्ट्रा-लोवाज़ (एलएलएल) जाली आधार कटौती [[कलन विधि]] एक बहुपद समय जाली कमी एल्गोरिथ्म है जिसका आविष्कार 1982 में [[अर्जेन लेनस्ट्रा]], [[हेनरी लेनस्ट्रा]] और लास्ज़लो लोवाज़ ने किया था।<ref>{{Cite journal|last1=Lenstra|first1=A. K.|author1-link=A. K. Lenstra|last2=Lenstra|first2=H. W., Jr.|author2-link=H. W. Lenstra, Jr.|last3=Lovász|first3=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>\mathbf{B} = \{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_d \}</math> एन-आयामी पूर्णांक निर्देशांक के साथ, एक [[जाली (समूह)]] एल ('आर' का एक अलग उपसमूह) के लिए<sup>n</sup>) के साथ <math> d \leq n </math>, एलएलएल एल्गोरिदम समय में एलएलएल-कम (छोटा, लगभग ओर्थोगोनल ) जाली आधार की गणना करता है <math display="block">\mathcal O(d^5n\log^3 B)</math> कहाँ <math>B</math> की सबसे बड़ी लंबाई है <math>\mathbf{b}_i</math> Norm_(mathematics)#Euclidean_norm के अंतर्गत, अर्थात, <math>B = \max\left(\|\mathbf{b}_1\|_2, \|\mathbf{b}_2\|_2, \dots, \|\mathbf{b}_d\|_2\right)</math>.<ref>{{Cite book|last1=Galbraith|first1=Steven|title=सार्वजनिक कुंजी क्रिप्टोग्राफी का गणित| year=2012|chapter=chapter 17|chapter-url=https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html}}</ref><ref>{{cite journal |last1=Nguyen |first1=Phong Q. |last2=Stehlè |first2=Damien |title=द्विघात जटिलता के साथ एक एलएलएल एल्गोरिदम|journal=SIAM J. Comput. |date=September 2009 |volume=39 |issue=3 |pages=874–903 |doi=10.1137/070705702 |url=https://dl.acm.org/citation.cfm?id=1655318 |access-date=3 June 2019}}</ref>
 
मूल अनुप्रयोग बहुपद गुणनखंडन के लिए बहुपद-समय एल्गोरिदम देने के लिए थे#पूर्णांकों पर अविभाज्य बहुपदों का गुणनखंडन करने के लिए, डिरिचलेट के सन्निकटन प्रमेय#एक साथ संस्करण को खोजने के लिए, और निश्चित आयामों में [[रैखिक प्रोग्रामिंग]] को हल करने के लिए।
'''लेनस्ट्रा-लेनस्ट्रा-लोवाज़ (एलएलएल) जालक (लैटिस) आधार कटौती [[कलन विधि]]''' एक बहुपद समय जालक कमी कलन विधि है जिसका आविष्कार 1982 में [[अर्जेन लेनस्ट्रा]], [[हेनरी लेनस्ट्रा]] और लास्ज़लो लोवाज़ ने किया था।<ref>{{Cite journal|last1=Lenstra|first1=A. K.|author1-link=A. K. Lenstra|last2=Lenstra|first2=H. W., Jr.|author2-link=H. W. Lenstra, Jr.|last3=Lovász|first3=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>\mathbf{B} = \{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_d \}</math> ''n''-आयामी पूर्णांक निर्देशांक के साथ, एक [[जाली (समूह)|जालक (समूह)]] एल (''''R'''<sup>''n''</sup>' का एक अलग उपसमूह) के साथ <math> d \leq n </math>, एलएलएल (LLL) कलन विधि (एल्गोरिदम) समय में एलएलएल-कम (लघु, लगभग ओर्थोगोनल ) जालक आधार की गणना करता है <math display="block">\mathcal O(d^5n\log^3 B)</math> जहाँ <math>B</math> की सबसे बड़ी लंबाई है <math>\mathbf{b}_i</math> यूक्लिडियन मानदंड के अंतर्गत, अर्थात, <math>B = \max\left(\|\mathbf{b}_1\|_2, \|\mathbf{b}_2\|_2, \dots, \|\mathbf{b}_d\|_2\right)</math>.<ref>{{Cite book|last1=Galbraith|first1=Steven|title=सार्वजनिक कुंजी क्रिप्टोग्राफी का गणित| year=2012|chapter=chapter 17|chapter-url=https://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html}}</ref><ref>{{cite journal |last1=Nguyen |first1=Phong Q. |last2=Stehlè |first2=Damien |title=द्विघात जटिलता के साथ एक एलएलएल एल्गोरिदम|journal=SIAM J. Comput. |date=September 2009 |volume=39 |issue=3 |pages=874–903 |doi=10.1137/070705702 |url=https://dl.acm.org/citation.cfm?id=1655318 |access-date=3 June 2019}}</ref>
मूल अनुप्रयोग बहुपद गुणनखंडन के लिए बहुपद-समय कलन विधि देने के लिए थे#पूर्णांकों पर अविभाज्य बहुपदों का गुणनखंडन करने के लिए, डिरिचलेट के सन्निकटन प्रमेय एक साथ संस्करण को खोजने के लिए, और निश्चित आयामों में [[रैखिक प्रोग्रामिंग]] को हल करने के लिए है।


==एलएलएल कमी==
==एलएलएल कमी==
एलएलएल-रिड्यूस्ड की सटीक परिभाषा इस प्रकार है: एक आधार दिया गया (रैखिक बीजगणित)
एलएलएल-रिड्यूस्ड की स्पष्ट परिभाषा इस प्रकार है: एक आधार दिया गया (रैखिक बीजगणित)
<math display="block">\mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_n \},</math>
<math display="block">\mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_n \},</math>
इसके ग्राम-श्मिट प्रक्रिया ऑर्थोगोनल आधार को परिभाषित करें
इसके ग्राम-श्मिट प्रक्रिया ऑर्थोगोनल आधार को परिभाषित करें
Line 12: Line 13:
<math display="block">\mu_{i,j}=\frac{\langle\mathbf{b}_i,\mathbf{b}^*_j\rangle}{\langle\mathbf{b}^*_j,\mathbf{b}^*_j\rangle},</math> किसी के लिए <math>1 \le j < i \le n</math>.
<math display="block">\mu_{i,j}=\frac{\langle\mathbf{b}_i,\mathbf{b}^*_j\rangle}{\langle\mathbf{b}^*_j,\mathbf{b}^*_j\rangle},</math> किसी के लिए <math>1 \le j < i \le n</math>.


फिर आधार <math>B</math> यदि कोई पैरामीटर मौजूद है तो एलएलएल कम हो गया है <math>\delta</math> में {{open-closed|0.25, 1}} ऐसा कि निम्नलिखित कायम रहे:
फिर आधार <math>B</math> यदि कोई पैरामीटर उपस्थित है तो एलएलएल कम हो गया है <math>\delta</math> में {{open-closed|0.25, 1}} ऐसा कि निम्नलिखित कायम रहे:


# (आकार-कम) के लिए <math>1 \leq j < i \leq n\colon \left|\mu_{i,j}\right|\leq 0.5</math>. परिभाषा के अनुसार, यह संपत्ति आदेशित आधार की लंबाई में कमी की गारंटी देती है।
# (आकार-कम) के लिए <math>1 \leq j < i \leq n\colon \left|\mu_{i,j}\right|\leq 0.5</math>. परिभाषा के अनुसार, यह संपत्ति आदेशित आधार की लंबाई में कमी की गारंटी देती है।
Line 18: Line 19:
  \mathbf{b}^*_{k-1}\Vert^2</math>.
  \mathbf{b}^*_{k-1}\Vert^2</math>.


यहां, के मूल्य का अनुमान लगाया जा रहा है <math>\delta</math> पैरामीटर, हम यह निष्कर्ष निकाल सकते हैं कि आधार कितनी अच्छी तरह कम हो गया है। के महानतम मूल्य <math>\delta</math> आधार की मजबूत कटौती का नेतृत्व करें। प्रारंभ में, ए. लेनस्ट्रा, एच. लेनस्ट्रा और एल. लोवेज़ ने एलएलएल-कमी एल्गोरिथ्म का प्रदर्शन किया <math>\delta = \frac{3}{4}</math>. ध्यान दें कि यद्यपि एलएलएल-कमी को अच्छी तरह से परिभाषित किया गया है <math>\delta = 1</math>, बहुपद-समय जटिलता की गारंटी केवल के लिए है <math>\delta</math> में <math>(0.25,1)</math>.
यहां, के मूल्य का अनुमान लगाया जा रहा है <math>\delta</math> पैरामीटर, हम यह निष्कर्ष निकाल सकते हैं कि आधार कितनी अच्छी तरह कम हो गया है। के महानतम मूल्य <math>\delta</math> आधार की मजबूत कटौती का नेतृत्व करें। प्रारंभ में, ए. लेनस्ट्रा, एच. लेनस्ट्रा और एल. लोवेज़ ने एलएलएल-कमी कलन विधि का प्रदर्शन किया <math>\delta = \frac{3}{4}</math>. ध्यान दें कि यद्यपि एलएलएल-कमी को अच्छी तरह से परिभाषित किया गया है <math>\delta = 1</math>, बहुपद-समय जटिलता की गारंटी केवल के लिए है <math>\delta</math> में <math>(0.25,1)</math>.


एलएलएल एल्गोरिदम एलएलएल-कम किए गए आधारों की गणना करता है। आधार की गणना करने के लिए कोई ज्ञात कुशल एल्गोरिदम नहीं है जिसमें 4 से अधिक आयामों की जाली के लिए आधार वैक्टर जितना संभव हो उतना छोटा हो।<ref>{{Cite journal|last1=Nguyen|first1=Phong Q.|last2=Stehlé|first2=Damien|date=1 October 2009|title=निम्न-आयामी जाली आधार कमी पर दोबारा गौर किया गया|journal=ACM Transactions on Algorithms |language=en|volume=5|issue=4|pages=1–48|doi=10.1145/1597036.1597050|s2cid=10583820}}</ref> हालाँकि, एलएलएल-कम आधार लगभग जितना संभव हो उतना छोटा है, इस अर्थ में कि पूर्ण सीमाएँ हैं <math>c_i > 1</math> ऐसा कि प्रथम आधार सदिश से अधिक नहीं है <math>c_1</math> जाली में सबसे छोटे वेक्टर से कई गुना लंबा,
एलएलएल कलन विधि एलएलएल-कम किए गए आधारों की गणना करता है। आधार की गणना करने के लिए कोई ज्ञात कुशल कलन विधि नहीं है जिसमें 4 से अधिक आयामों की जालक के लिए आधार सदिश जितना संभव हो उतना लघु हो।<ref>{{Cite journal|last1=Nguyen|first1=Phong Q.|last2=Stehlé|first2=Damien|date=1 October 2009|title=निम्न-आयामी जाली आधार कमी पर दोबारा गौर किया गया|journal=ACM Transactions on Algorithms |language=en|volume=5|issue=4|pages=1–48|doi=10.1145/1597036.1597050|s2cid=10583820}}</ref> हालाँकि, एलएलएल-कम आधार लगभग जितना संभव हो उतना लघु है, इस अर्थ में कि पूर्ण सीमाएँ हैं <math>c_i > 1</math> ऐसा कि प्रथम आधार सदिश से अधिक नहीं है <math>c_1</math> जालक में सबसे छोटे सदिश से कई गुना लंबा, दूसरा आधार सदिश भी इसी प्रकार अंदर है <math>c_2</math> दूसरे क्रमिक न्यूनतम का, इत्यादि।
दूसरा आधार वेक्टर भी इसी प्रकार भीतर है <math>c_2</math> दूसरे क्रमिक न्यूनतम का, इत्यादि।


==अनुप्रयोग==
==अनुप्रयोग==
एलएलएल एल्गोरिथ्म का एक प्रारंभिक सफल अनुप्रयोग [[एंड्रयू ओडलीज़्को]] और [[रीले में हरमन]] द्वारा [[मर्टेंस अनुमान]] अनुमान को खारिज करने में इसका उपयोग था।<ref>{{cite journal |last1=Odlyzko |first1=Andrew |last2=te Reile |first2=Herman J. J. |title=मर्टेंस अनुमान का खंडन करना|journal=[[Journal für die reine und angewandte Mathematik]] |volume=357 |pages=138–160 |doi=10.1515/crll.1985.357.138 |s2cid=13016831 |url=http://www.dtc.umn.edu/~odlyzko/doc/arch/mertens.disproof.pdf |access-date=27 January 2020}}</ref>
एलएलएल कलन विधि का एक प्रारंभिक सफल अनुप्रयोग एंड्रयू ओडलीज़्को और रीले में हरमन द्वारा [[मर्टेंस अनुमान]] अनुमान को खारिज करने में इसका उपयोग था।<ref>{{cite journal |last1=Odlyzko |first1=Andrew |last2=te Reile |first2=Herman J. J. |title=मर्टेंस अनुमान का खंडन करना|journal=[[Journal für die reine und angewandte Mathematik]] |volume=357 |pages=138–160 |doi=10.1515/crll.1985.357.138 |s2cid=13016831 |url=http://www.dtc.umn.edu/~odlyzko/doc/arch/mertens.disproof.pdf |access-date=27 January 2020}}</ref>
एलएलएल एल्गोरिदम को एमआईएमओ डिटेक्शन एल्गोरिदम में कई अन्य अनुप्रयोग मिले हैं<ref>D. Wübben et al., "Lattice reduction," IEEE Signal Processing Magazine, Vol. 28, No. 3, pp. 70-91, Apr. 2011.</ref> और [[सार्वजनिक-कुंजी एन्क्रिप्शन]] योजनाओं का क्रिप्टो विश्लेषण: [[नैकाचे-स्टर्न नैपसैक क्रिप्टोसिस्टम]], विशेष सेटिंग्स के साथ [[आरएसए (एल्गोरिदम)]], [[एनटीआरयूएन्क्रिप्ट]], इत्यादि। एल्गोरिदम का उपयोग कई समस्याओं के पूर्णांक समाधान खोजने के लिए किया जा सकता है।<ref>{{Cite journal| author=D. Simon |title=संख्या सिद्धांत में एलएलएल के चयनित अनुप्रयोग|journal=LLL+25 Conference |year=2007 |place=Caen, France | url=https://simond.users.lmno.cnrs.fr/maths/lll25_Simon.pdf}}</ref>
एलएलएल कलन विधि को एमआईएमओ डिटेक्शन कलन विधि में कई अन्य अनुप्रयोग मिले हैं<ref>D. Wübben et al., "Lattice reduction," IEEE Signal Processing Magazine, Vol. 28, No. 3, pp. 70-91, Apr. 2011.</ref> और [[सार्वजनिक-कुंजी एन्क्रिप्शन]] योजनाओं का क्रिप्टो विश्लेषण: [[नैकाचे-स्टर्न नैपसैक क्रिप्टोसिस्टम]], विशेष सेटिंग्स के साथ [[आरएसए (एल्गोरिदम)|आरएसए (कलन विधि)]], [[एनटीआरयूएन्क्रिप्ट]], इत्यादि। कलन विधि का उपयोग कई समस्याओं के पूर्णांक समाधान खोजने के लिए किया जा सकता है।<ref>{{Cite journal| author=D. Simon |title=संख्या सिद्धांत में एलएलएल के चयनित अनुप्रयोग|journal=LLL+25 Conference |year=2007 |place=Caen, France | url=https://simond.users.lmno.cnrs.fr/maths/lll25_Simon.pdf}}</ref>
विशेष रूप से, एलएलएल एल्गोरिदम पूर्णांक संबंध एल्गोरिदम में से एक का मूल बनाता है। उदाहरण के लिए, यदि यह माना जाता है कि r=1.618034 पूर्णांक गुणांक वाले अज्ञात [[द्विघात समीकरण]] के लिए एक फ़ंक्शन का (थोड़ा गोलाकार) मूल है, तो कोई जाली में एलएलएल कटौती लागू कर सकता है <math>\mathbf{Z}^4</math> द्वारा फैलाया गया <math>[1,0,0,10000r^2], [0,1,0,10000r],</math> और <math>[0,0,1,10000]</math>. घटे हुए आधार में पहला वेक्टर इन तीनों का एक पूर्णांक [[रैखिक संयोजन]] होगा, इस प्रकार आवश्यक रूप से <math>[a,b,c,10000(ar^2+br+c)]</math>; लेकिन ऐसा वेक्टर केवल तभी छोटा होता है जब a, b, c छोटे हों और <math>ar^2+br+c</math> और भी छोटा है. इस प्रकार इस लघु वेक्टर की पहली तीन प्रविष्टियाँ अभिन्न द्विघात [[बहुपद]] के गुणांक होने की संभावना है जिसका मूल r है। इस उदाहरण में एलएलएल एल्गोरिदम सबसे छोटा वेक्टर पाता है [1, -1, -1, 0.00025] और वास्तव में <math>x^2-x-1</math> इसका मूल स्वर्णिम अनुपात के बराबर है, 1.6180339887....
विशेष रूप से, एलएलएल कलन विधि पूर्णांक संबंध कलन विधि में से एक का मूल बनाता है। उदाहरण के लिए, यदि यह माना जाता है कि r=1.618034 पूर्णांक गुणांक वाले अज्ञात [[द्विघात समीकरण]] के लिए एक फलन का (थोड़ा गोलाकार) मूल है, तो कोई जालक में एलएलएल कटौती लागू कर सकता है <math>\mathbf{Z}^4</math> द्वारा प्रसारित किया गया <math>[1,0,0,10000r^2], [0,1,0,10000r],</math> और <math>[0,0,1,10000]</math>. घटे हुए आधार में पहला सदिश इन तीनों का एक पूर्णांक [[रैखिक संयोजन]] होगा, इस प्रकार आवश्यक रूप से <math>[a,b,c,10000(ar^2+br+c)]</math>; लेकिन ऐसा सदिश केवल तभी लघु होता है जब a, b, c छोटे हों और <math>ar^2+br+c</math> और भी लघु है. इस प्रकार इस लघु सदिश की पहली तीन प्रविष्टियाँ अभिन्न द्विघात [[बहुपद]] के गुणांक होने की संभावना है जिसका मूल r है। इस उदाहरण में एलएलएल कलन विधि सबसे लघु सदिश पाता है [1, -1, -1, 0.00025] और वास्तव में <math>x^2-x-1</math> इसका मूल स्वर्णिम अनुपात के बराबर है, 1.6180339887....


==एलएल-कम आधार के गुण==
==एलएल-कम आधार के गुण==
होने देना <math>\mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_n \}</math> एक हो <math>\delta</math>-एलएलएल-एक जाली का कम आधार (समूह) <math>\mathcal L</math>. एलएलएल-कम आधार की परिभाषा से, हम इसके बारे में कई अन्य उपयोगी गुण प्राप्त कर सकते हैं <math>\mathbf{B}</math>.
होने देना <math>\mathbf{B}=\{ \mathbf{b}_1,\mathbf{b}_2, \dots, \mathbf{b}_n \}</math> एक हो <math>\delta</math>-एलएलएल-एक जालक का कम आधार (समूह) <math>\mathcal L</math>. एलएलएल-कम आधार की परिभाषा से, हम इसके बारे में कई अन्य उपयोगी गुण प्राप्त कर सकते हैं <math>\mathbf{B}</math>.


# आधार में पहला वेक्टर लैटिस समस्या से बहुत बड़ा नहीं हो सकता # सबसे छोटा वेक्टर समस्या (एसवीपी) | सबसे छोटा गैर-शून्य वेक्टर: <math>\Vert\mathbf{b}_1 \Vert \le (2 / (\sqrt{4\delta - 1}))^{n-1} \cdot \lambda_1(\mathcal L)</math>. विशेष रूप से, के लिए <math>\delta = 3/4</math>, यह देता है <math>\Vert\mathbf{b}_1 \Vert \le 2^{(n-1)/2} \cdot \lambda_1(\mathcal L)</math>.<ref name="regev_lll">{{cite web |last1=Regev |first1=Oded |title=कंप्यूटर विज्ञान में लैटिस: एलएलएल एल्गोरिथम|url=https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/lll.pdf#page=3 |publisher=New York University |access-date=1 February 2019}}</ref>
# आधार में पहला सदिश लैटिस समस्या से बहुत बड़ा नहीं हो सकता # सबसे लघु सदिश समस्या (एसवीपी) | सबसे लघु गैर-शून्य सदिश: <math>\Vert\mathbf{b}_1 \Vert \le (2 / (\sqrt{4\delta - 1}))^{n-1} \cdot \lambda_1(\mathcal L)</math>. विशेष रूप से, के लिए <math>\delta = 3/4</math>, यह देता है <math>\Vert\mathbf{b}_1 \Vert \le 2^{(n-1)/2} \cdot \lambda_1(\mathcal L)</math>.<ref name="regev_lll">{{cite web |last1=Regev |first1=Oded |title=कंप्यूटर विज्ञान में लैटिस: एलएलएल एल्गोरिथम|url=https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/lll.pdf#page=3 |publisher=New York University |access-date=1 February 2019}}</ref>
# आधार में पहला वेक्टर भी जाली के निर्धारक से घिरा है: <math>\Vert\mathbf{b}_1 \Vert \le (2 / (\sqrt{4\delta - 1}))^{(n-1)/2} \cdot (\det(\mathcal L))^{1/n}</math>. विशेष रूप से, के लिए <math>\delta = 3/4</math>, यह देता है <math>\Vert\mathbf{b}_1 \Vert \le 2^{(n-1)/4} \cdot  (\det(\mathcal L))^{1/n}</math>.
# आधार में पहला सदिश भी जालक के निर्धारक से घिरा है: <math>\Vert\mathbf{b}_1 \Vert \le (2 / (\sqrt{4\delta - 1}))^{(n-1)/2} \cdot (\det(\mathcal L))^{1/n}</math>. विशेष रूप से, के लिए <math>\delta = 3/4</math>, यह देता है <math>\Vert\mathbf{b}_1 \Vert \le 2^{(n-1)/4} \cdot  (\det(\mathcal L))^{1/n}</math>.
# आधार में वैक्टर के मानदंडों का उत्पाद जाली के निर्धारक से बहुत बड़ा नहीं हो सकता: चलो <math>\delta = 3/4</math>, तब  <math display="inline">\prod_{i=1}^n \Vert\mathbf{b}_i \Vert \le 2^{n(n-1)/4} \cdot  \det(\mathcal L)</math>.
# आधार में सदिश के मानदंडों का उत्पाद जालक के निर्धारक से बहुत बड़ा नहीं हो सकता: चलो <math>\delta = 3/4</math>, तब  <math display="inline">\prod_{i=1}^n \Vert\mathbf{b}_i \Vert \le 2^{n(n-1)/4} \cdot  \det(\mathcal L)</math>.


==एलएलएल एल्गोरिदम स्यूडोकोड==
==एलएलएल कलन विधि स्यूडोकोड==
निम्नलिखित विवरण पर आधारित है {{harv|Hoffstein|Pipher|Silverman|2008|loc=Theorem 6.68}}, इरेटा से सुधार के साथ।<ref>{{cite web| last1=Silverman| first1=Joseph| title=गणितीय क्रिप्टोग्राफी इरेटा का परिचय|url=http://www.math.brown.edu/~jhs/MathCrypto/MathCryptoErrata.pdf|website=Brown University Mathematics Dept.| access-date=5 May 2015}}</ref>
निम्नलिखित विवरण पर आधारित है {{harv|हॉफस्टीन|पिफर|सिल्वरमैन|2008|loc=प्रमेय 6.68}}, इरेटा से सुधार के साथ है।<ref>{{cite web| last1=Silverman| first1=Joseph| title=गणितीय क्रिप्टोग्राफी इरेटा का परिचय|url=http://www.math.brown.edu/~jhs/MathCrypto/MathCryptoErrata.pdf|website=Brown University Mathematics Dept.| access-date=5 May 2015}}</ref>
  '''INPUT'''
  '''INPUT'''
     a lattice basis '''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''n''</sub> in '''Z'''<sup>''m''</sup>
     a lattice basis '''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''n''</sub> in '''Z'''<sup>''m''</sup>
Line 65: Line 65:
     the reduced basis '''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''n''</sub> in '''Z'''<sup>''m''</sup>
     the reduced basis '''b'''<sub>1</sub>, '''b'''<sub>2</sub>, ..., '''b'''<sub>''n''</sub> in '''Z'''<sup>''m''</sup>


[[Category:Articles with invalid date parameter in template|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
 
[[Category:Collapse templates|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
 
[[Category:Created On 14/07/2023|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
 
[[Category:Machine Translated Page|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
 
[[Category:Navigational boxes| ]]
 
[[Category:Navigational boxes without horizontal lists|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
 
[[Category:Pages with script errors|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
 
[[Category:Short description with empty Wikidata description|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
 
[[Category:Sidebars with styles needing conversion|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
 
[[Category:Template documentation pages|Documentation/doc]]
 


==उदाहरण==
==उदाहरण==
Line 80: Line 80:
=== Z से उदाहरण<sup>3</sup>===
=== Z से उदाहरण<sup>3</sup>===


चलो एक जाली आधार <math> \mathbf{b}_1,\mathbf{b}_2, \mathbf{b}_3 \in \mathbf{Z}^{3}</math>, के कॉलम द्वारा दिया जाए
चलो एक जालक आधार <math> \mathbf{b}_1,\mathbf{b}_2, \mathbf{b}_3 \in \mathbf{Z}^{3}</math>, के कॉलम द्वारा दिया जाए
<math display="block">\begin{bmatrix}
<math display="block">\begin{bmatrix}
   1 & -1& 3\\
   1 & -1& 3\\
Line 92: Line 92:
   0 & 1 & 2
   0 & 1 & 2
\end{bmatrix},</math>
\end{bmatrix},</math>
जो आकार में छोटा है, लोवेज़ स्थिति को संतुष्ट करता है, और इसलिए एलएलएल-कम हो गया है, जैसा कि ऊपर वर्णित है। डब्ल्यू बोस्मा देखें।<ref>{{Cite web| url=http://www.math.ru.nl/~bosma/onderwijs/voorjaar07/compalg7.pdf|title=4. LLL |last=Bosma|first=Wieb|work=Lecture notes|access-date=28 February 2010}}</ref> कमी प्रक्रिया के विवरण के लिए.
जो आकार में लघु है, लोवेज़ स्थिति को संतुष्ट करता है, और इसलिए एलएलएल-कम हो गया है, जैसा कि ऊपर वर्णित है। डब्ल्यू बोस्मा देखें।<ref>{{Cite web| url=http://www.math.ru.nl/~bosma/onderwijs/voorjaar07/compalg7.pdf|title=4. LLL |last=Bosma|first=Wieb|work=Lecture notes|access-date=28 February 2010}}</ref> कमी प्रक्रिया के विवरण के लिए.


=== Z[i] से उदाहरण<sup>4</sup>===
=== Z[i] से उदाहरण<sup>4</sup>===
इसी प्रकार, नीचे मैट्रिक्स के कॉलम द्वारा दिए गए जटिल पूर्णांकों के आधार के लिए,
इसी प्रकार, नीचे आव्यूह के कॉलम द्वारा दिए गए जटिल पूर्णांकों के आधार के लिए,
<math display="block">\begin{bmatrix}
<math display="block">\begin{bmatrix}
  -2+2i &  7+3i &  7+3i & -5+4i\\
  -2+2i &  7+3i &  7+3i & -5+4i\\
Line 102: Line 102:
   8+2i & -9+0i &  6+3i & -4+4i
   8+2i & -9+0i &  6+3i & -4+4i
\end{bmatrix},</math>
\end{bmatrix},</math>
तो नीचे मैट्रिक्स के कॉलम एलएलएल-कम आधार देते हैं।
तो नीचे आव्यूह के कॉलम एलएलएल-कम आधार देते हैं।
<math display="block">\begin{bmatrix}
<math display="block">\begin{bmatrix}
  -6+3i & -2+2i &  2-2i & -3+6i \\
  -6+3i & -2+2i &  2-2i & -3+6i \\
   6-1i &  3+3i &  5-5i &  2+1i \\
   6-1i &  3+3i &  5-5i &  2+1i \\
Line 113: Line 113:
==कार्यान्वयन==
==कार्यान्वयन==
एलएलएल में लागू किया गया है
एलएलएल में लागू किया गया है
*[http://www.arageli.org/ अरागेली] फ़ंक्शन के रूप में <code>lll_reduction_int</code>
*[http://www.arageli.org/ अरागेली] फलन के रूप में <code>lll_reduction_int</code>
*[https://github.com/fplll/fplll fpLLL] एक स्टैंड-अलोन कार्यान्वयन के रूप में
*[https://github.com/fplll/fplll fpLLL] एक स्टैंड-अलोन कार्यान्वयन के रूप में
*कार्यक्रम के रूप में [[संख्या सिद्धांत के लिए फास्ट लाइब्रेरी]] <code>fmpz_lll</code>
*कार्यक्रम के रूप में [[संख्या सिद्धांत के लिए फास्ट लाइब्रेरी]] <code>fmpz_lll</code>
* फ़ंक्शन के रूप में [[GAP कंप्यूटर बीजगणित प्रणाली]] <code>LLLReducedBasis</code>
* फलन के रूप में [[GAP कंप्यूटर बीजगणित प्रणाली]] <code>LLLReducedBasis</code>
*[[खुश]] फ़ंक्शन के रूप में <code>LLL</code> पैकेज में <code>LLLBases</code>
*फलन के रूप में <code>LLL</code> पैकेज में <code>LLLBases</code>
*[[मैग्मा कंप्यूटर बीजगणित प्रणाली]] के कार्य <code>LLL</code> और <code>LLLGram</code> (ग्राम मैट्रिक्स लेते हुए)
*[[मैग्मा कंप्यूटर बीजगणित प्रणाली]] के कार्य <code>LLL</code> और <code>LLLGram</code> (ग्राम आव्यूह लेते हुए)
*[[मेपल कंप्यूटर बीजगणित प्रणाली]] फ़ंक्शन के रूप में <code>IntegerRelations[LLL]</code>
*[[मेपल कंप्यूटर बीजगणित प्रणाली]] फलन के रूप में <code>IntegerRelations[LLL]</code>
*फ़ंक्शन के रूप में गणित <code>LatticeReduce</code>
*फलन के रूप में गणित <code>LatticeReduce</code>
*[https://github.com/libntl/ntl नंबर थ्योरी लाइब्रेरी (NTL)] फ़ंक्शन के रूप में <code>LLL</code>
*[https://github.com/libntl/ntl नंबर थ्योरी लाइब्रेरी (NTL)] फलन के रूप में <code>LLL</code>
*कार्यक्रम के रूप में PARI/GP <code>qflll</code>
*कार्यक्रम के रूप में PARI/GP <code>qflll</code>
*[http://pymatgen.org/ Pymatgen] फ़ंक्शन के रूप में <code>analysis.get_lll_reduced_lattice</code>
*[http://pymatgen.org/ Pymatgen] फलन के रूप में <code>analysis.get_lll_reduced_lattice</code>
*विधि के रूप में [[सेजमैथ]] <code>LLL</code> एफपीएलएलएल और एनटीएल द्वारा संचालित
*विधि के रूप में [[सेजमैथ]] <code>LLL</code> एफपीएलएलएल और एनटीएल द्वारा संचालित
*इसाबेल/एचओएल 'औपचारिक साक्ष्यों के संग्रह' प्रविष्टि में <code>LLL_Basis_Reduction</code>. यह कोड कुशलतापूर्वक निष्पादन योग्य हास्केल को निर्यात करता है।<ref>{{Cite journal|title=एलएलएल बेसिस रिडक्शन एल्गोरिदम का औपचारिकीकरण|last=Divasón|first=Jose|journal=Conference Paper|series=Lecture Notes in Computer Science |year=2018 |volume=10895 |pages=160–177 |doi=10.1007/978-3-319-94821-8_10 |isbn=978-3-319-94820-1 |doi-access=free }}</ref>
*इसाबेल/एचओएल 'औपचारिक साक्ष्यों के संग्रह' प्रविष्टि में <code>LLL_Basis_Reduction</code>. यह कोड कुशलतापूर्वक निष्पादन योग्य हास्केल को निर्यात करता है।<ref>{{Cite journal|title=एलएलएल बेसिस रिडक्शन एल्गोरिदम का औपचारिकीकरण|last=Divasón|first=Jose|journal=Conference Paper|series=Lecture Notes in Computer Science |year=2018 |volume=10895 |pages=160–177 |doi=10.1007/978-3-319-94821-8_10 |isbn=978-3-319-94820-1 |doi-access=free }}</ref>
==यह भी देखें==
==यह भी देखें==
*कॉपरस्मिथ विधि
*कॉपरस्मिथ विधि
Line 133: Line 131:
==टिप्पणियाँ==
==टिप्पणियाँ==
{{Reflist}}
{{Reflist}}
==संदर्भ==
==संदर्भ==
* {{cite journal|first1=Huguette |last1=Napias
* {{cite journal|first1=Huguette |last1=Napias
Line 165: Line 161:
{{Number-theoretic algorithms}}
{{Number-theoretic algorithms}}


{{DEFAULTSORT:Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm}}[[Category: क्रिप्टोग्राफी का सिद्धांत]] [[Category: कम्प्यूटेशनल संख्या सिद्धांत]] [[Category: जाली बिंदु]]
{{DEFAULTSORT:Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm}}


 
[[Category:Articles with invalid date parameter in template|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
 
[[Category:CS1 English-language sources (en)]]
[[Category: Machine Translated Page]]
[[Category:Collapse templates|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Created On 14/07/2023]]
[[Category:Created On 14/07/2023|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Lua-based templates|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Machine Translated Page|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Pages with script errors|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Short description with empty Wikidata description|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Sidebars with styles needing conversion|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Translated in Hindi|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Templates Vigyan Ready|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Templates generating microformats|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Templates that add a tracking category|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Templates that are not mobile friendly|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Templates that generate short descriptions|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Templates using TemplateData|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:Wikipedia metatemplates|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:कम्प्यूटेशनल संख्या सिद्धांत|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:क्रिप्टोग्राफी का सिद्धांत|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]
[[Category:जाली बिंदु|Lenstra-Lenstra-Lovasz Lattice Basis Reduction Algorithm]]

Latest revision as of 10:55, 7 August 2023


लेनस्ट्रा-लेनस्ट्रा-लोवाज़ (एलएलएल) जालक (लैटिस) आधार कटौती कलन विधि एक बहुपद समय जालक कमी कलन विधि है जिसका आविष्कार 1982 में अर्जेन लेनस्ट्रा, हेनरी लेनस्ट्रा और लास्ज़लो लोवाज़ ने किया था।[1] एक आधार दिया गया (रैखिक बीजगणित) n-आयामी पूर्णांक निर्देशांक के साथ, एक जालक (समूह) एल ('Rn' का एक अलग उपसमूह) के साथ , एलएलएल (LLL) कलन विधि (एल्गोरिदम) समय में एलएलएल-कम (लघु, लगभग ओर्थोगोनल ) जालक आधार की गणना करता है

जहाँ की सबसे बड़ी लंबाई है यूक्लिडियन मानदंड के अंतर्गत, अर्थात, .[2][3] मूल अनुप्रयोग बहुपद गुणनखंडन के लिए बहुपद-समय कलन विधि देने के लिए थे#पूर्णांकों पर अविभाज्य बहुपदों का गुणनखंडन करने के लिए, डिरिचलेट के सन्निकटन प्रमेय एक साथ संस्करण को खोजने के लिए, और निश्चित आयामों में रैखिक प्रोग्रामिंग को हल करने के लिए है।

एलएलएल कमी

एलएलएल-रिड्यूस्ड की स्पष्ट परिभाषा इस प्रकार है: एक आधार दिया गया (रैखिक बीजगणित)

इसके ग्राम-श्मिट प्रक्रिया ऑर्थोगोनल आधार को परिभाषित करें
और ग्राम-श्मिट गुणांक
किसी के लिए .

फिर आधार यदि कोई पैरामीटर उपस्थित है तो एलएलएल कम हो गया है में (0.25, 1] ऐसा कि निम्नलिखित कायम रहे:

  1. (आकार-कम) के लिए . परिभाषा के अनुसार, यह संपत्ति आदेशित आधार की लंबाई में कमी की गारंटी देती है।
  2. (लोवेज़ स्थिति) k = 2,3,..,n के लिए .

यहां, के मूल्य का अनुमान लगाया जा रहा है पैरामीटर, हम यह निष्कर्ष निकाल सकते हैं कि आधार कितनी अच्छी तरह कम हो गया है। के महानतम मूल्य आधार की मजबूत कटौती का नेतृत्व करें। प्रारंभ में, ए. लेनस्ट्रा, एच. लेनस्ट्रा और एल. लोवेज़ ने एलएलएल-कमी कलन विधि का प्रदर्शन किया . ध्यान दें कि यद्यपि एलएलएल-कमी को अच्छी तरह से परिभाषित किया गया है , बहुपद-समय जटिलता की गारंटी केवल के लिए है में .

एलएलएल कलन विधि एलएलएल-कम किए गए आधारों की गणना करता है। आधार की गणना करने के लिए कोई ज्ञात कुशल कलन विधि नहीं है जिसमें 4 से अधिक आयामों की जालक के लिए आधार सदिश जितना संभव हो उतना लघु हो।[4] हालाँकि, एलएलएल-कम आधार लगभग जितना संभव हो उतना लघु है, इस अर्थ में कि पूर्ण सीमाएँ हैं ऐसा कि प्रथम आधार सदिश से अधिक नहीं है जालक में सबसे छोटे सदिश से कई गुना लंबा, दूसरा आधार सदिश भी इसी प्रकार अंदर है दूसरे क्रमिक न्यूनतम का, इत्यादि।

अनुप्रयोग

एलएलएल कलन विधि का एक प्रारंभिक सफल अनुप्रयोग एंड्रयू ओडलीज़्को और रीले में हरमन द्वारा मर्टेंस अनुमान अनुमान को खारिज करने में इसका उपयोग था।[5] एलएलएल कलन विधि को एमआईएमओ डिटेक्शन कलन विधि में कई अन्य अनुप्रयोग मिले हैं[6] और सार्वजनिक-कुंजी एन्क्रिप्शन योजनाओं का क्रिप्टो विश्लेषण: नैकाचे-स्टर्न नैपसैक क्रिप्टोसिस्टम, विशेष सेटिंग्स के साथ आरएसए (कलन विधि), एनटीआरयूएन्क्रिप्ट, इत्यादि। कलन विधि का उपयोग कई समस्याओं के पूर्णांक समाधान खोजने के लिए किया जा सकता है।[7] विशेष रूप से, एलएलएल कलन विधि पूर्णांक संबंध कलन विधि में से एक का मूल बनाता है। उदाहरण के लिए, यदि यह माना जाता है कि r=1.618034 पूर्णांक गुणांक वाले अज्ञात द्विघात समीकरण के लिए एक फलन का (थोड़ा गोलाकार) मूल है, तो कोई जालक में एलएलएल कटौती लागू कर सकता है द्वारा प्रसारित किया गया और . घटे हुए आधार में पहला सदिश इन तीनों का एक पूर्णांक रैखिक संयोजन होगा, इस प्रकार आवश्यक रूप से ; लेकिन ऐसा सदिश केवल तभी लघु होता है जब a, b, c छोटे हों और और भी लघु है. इस प्रकार इस लघु सदिश की पहली तीन प्रविष्टियाँ अभिन्न द्विघात बहुपद के गुणांक होने की संभावना है जिसका मूल r है। इस उदाहरण में एलएलएल कलन विधि सबसे लघु सदिश पाता है [1, -1, -1, 0.00025] और वास्तव में इसका मूल स्वर्णिम अनुपात के बराबर है, 1.6180339887....

एलएल-कम आधार के गुण

होने देना एक हो -एलएलएल-एक जालक का कम आधार (समूह) . एलएलएल-कम आधार की परिभाषा से, हम इसके बारे में कई अन्य उपयोगी गुण प्राप्त कर सकते हैं .

  1. आधार में पहला सदिश लैटिस समस्या से बहुत बड़ा नहीं हो सकता # सबसे लघु सदिश समस्या (एसवीपी) | सबसे लघु गैर-शून्य सदिश: . विशेष रूप से, के लिए , यह देता है .[8]
  2. आधार में पहला सदिश भी जालक के निर्धारक से घिरा है: . विशेष रूप से, के लिए , यह देता है .
  3. आधार में सदिश के मानदंडों का उत्पाद जालक के निर्धारक से बहुत बड़ा नहीं हो सकता: चलो , तब .

एलएलएल कलन विधि स्यूडोकोड

निम्नलिखित विवरण पर आधारित है (हॉफस्टीन, पिफर & सिल्वरमैन 2008, प्रमेय 6.68), इरेटा से सुधार के साथ है।[9]

INPUT
    a lattice basis b1, b2, ..., bn in Zm
    a parameter δ with 1/4 < δ < 1, most commonly δ = 3/4
PROCEDURE
    B* <- GramSchmidt({b1, ..., bn}) = {b1*, ..., bn*};  and do not normalize
    μi,j <- InnerProduct(bi, bj*)/InnerProduct(bj*, bj*);   using the most current values of bi and bj*
    k <- 2;
    while k <= n do
        for j from k−1 to 1 do
            if |μk,j| > 1/2 then
                bk <- bk − ⌊μk,jbj;
               Update B* and the related μi,j's as needed.
               (The naive method is to recompute B* whenever bi changes:
                B* <- GramSchmidt({b1, ..., bn}) = {b1*, ..., bn*})
            end if
        end for
        if InnerProduct(bk*, bk*) > (δ − μ2k,k−1) InnerProduct(bk−1*, bk−1*) then
            k <- k + 1;
        else
            Swap bk and  bk−1;
            Update B* and the related μi,j's as needed.
            k <- max(k−1, 2);
        end if
    end while
    return B the LLL reduced basis of {b1, ..., bn}
OUTPUT
    the reduced basis b1, b2, ..., bn in Zm







उदाहरण

Z से उदाहरण3

चलो एक जालक आधार , के कॉलम द्वारा दिया जाए

तो घटा हुआ आधार है

जो आकार में लघु है, लोवेज़ स्थिति को संतुष्ट करता है, और इसलिए एलएलएल-कम हो गया है, जैसा कि ऊपर वर्णित है। डब्ल्यू बोस्मा देखें।[10] कमी प्रक्रिया के विवरण के लिए.

Z[i] से उदाहरण4

इसी प्रकार, नीचे आव्यूह के कॉलम द्वारा दिए गए जटिल पूर्णांकों के आधार के लिए,

तो नीचे आव्यूह के कॉलम एलएलएल-कम आधार देते हैं।


कार्यान्वयन

एलएलएल में लागू किया गया है

यह भी देखें

  • कॉपरस्मिथ विधि

टिप्पणियाँ

  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.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  2. Galbraith, Steven (2012). "chapter 17". सार्वजनिक कुंजी क्रिप्टोग्राफी का गणित.
  3. Nguyen, Phong Q.; Stehlè, Damien (September 2009). "द्विघात जटिलता के साथ एक एलएलएल एल्गोरिदम". SIAM J. Comput. 39 (3): 874–903. doi:10.1137/070705702. Retrieved 3 June 2019.
  4. Nguyen, Phong Q.; Stehlé, Damien (1 October 2009). "निम्न-आयामी जाली आधार कमी पर दोबारा गौर किया गया". ACM Transactions on Algorithms (in English). 5 (4): 1–48. doi:10.1145/1597036.1597050. S2CID 10583820.
  5. Odlyzko, Andrew; te Reile, Herman J. J. "मर्टेंस अनुमान का खंडन करना" (PDF). Journal für die reine und angewandte Mathematik. 357: 138–160. doi:10.1515/crll.1985.357.138. S2CID 13016831. Retrieved 27 January 2020.
  6. D. Wübben et al., "Lattice reduction," IEEE Signal Processing Magazine, Vol. 28, No. 3, pp. 70-91, Apr. 2011.
  7. D. Simon (2007). "संख्या सिद्धांत में एलएलएल के चयनित अनुप्रयोग" (PDF). LLL+25 Conference. Caen, France.
  8. Regev, Oded. "कंप्यूटर विज्ञान में लैटिस: एलएलएल एल्गोरिथम" (PDF). New York University. Retrieved 1 February 2019.
  9. Silverman, Joseph. "गणितीय क्रिप्टोग्राफी इरेटा का परिचय" (PDF). Brown University Mathematics Dept. Retrieved 5 May 2015.
  10. Bosma, Wieb. "4. LLL" (PDF). Lecture notes. Retrieved 28 February 2010.
  11. Divasón, Jose (2018). "एलएलएल बेसिस रिडक्शन एल्गोरिदम का औपचारिकीकरण". Conference Paper. Lecture Notes in Computer Science. 10895: 160–177. doi:10.1007/978-3-319-94821-8_10. ISBN 978-3-319-94820-1.

संदर्भ