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

From Vigyanwiki

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

कहाँ की सबसे बड़ी लंबाई है Norm_(mathematics)#Euclidean_norm के अंतर्गत, अर्थात, .[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. आधार में वैक्टर के मानदंडों का उत्पाद जाली के निर्धारक से बहुत बड़ा नहीं हो सकता: चलो , तब .

एलएलएल एल्गोरिदम स्यूडोकोड

निम्नलिखित विवरण पर आधारित है (Hoffstein, Pipher & Silverman 2008, Theorem 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.


संदर्भ