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

From Vigyanwiki
(No difference)

Revision as of 13:57, 6 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.

संदर्भ