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

लेनस्ट्रा-लेनस्ट्रा-लोवाज़ (एलएलएल) जाली आधार कटौती कलन विधि एक बहुपद समय जाली कमी एल्गोरिथ्म है जिसका आविष्कार 1982 में अर्जेन लेनस्ट्रा, हेनरी लेनस्ट्रा और लास्ज़लो लोवाज़ ने किया था। एक आधार दिया गया (रैखिक बीजगणित) $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ एन-आयामी पूर्णांक निर्देशांक के साथ, एक जाली (समूह) एल ('आर' का एक अलग उपसमूह) के लिएⁿ) के साथ $d\leq n$, एलएलएल एल्गोरिदम समय में एलएलएल-कम (छोटा, लगभग ओर्थोगोनल ) जाली आधार की गणना करता है

$${\mathcal {O}}(d^{5}n\log ^{3}B)$$

कहाँ $B$ की सबसे बड़ी लंबाई है $\mathbf {b} _{i}$ Norm_(mathematics)#Euclidean_norm के अंतर्गत, अर्थात, $B=\max \left(\|\mathbf {b} _{1}\|_{2},\|\mathbf {b} _{2}\|_{2},\dots ,\|\mathbf {b} _{d}\|_{2}\right)$. मूल अनुप्रयोग बहुपद गुणनखंडन के लिए बहुपद-समय एल्गोरिदम देने के लिए थे#पूर्णांकों पर अविभाज्य बहुपदों का गुणनखंडन करने के लिए, डिरिचलेट के सन्निकटन प्रमेय#एक साथ संस्करण को खोजने के लिए, और निश्चित आयामों में रैखिक प्रोग्रामिंग को हल करने के लिए।

एलएलएल कमी

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

$$\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\},$$

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

$$\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},$$

और ग्राम-श्मिट गुणांक

$$\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }},$$

किसी के लिए $1\leq j<i\leq n$.

फिर आधार $B$ यदि कोई पैरामीटर मौजूद है तो एलएलएल कम हो गया है $\delta$ में (0.25, 1] ऐसा कि निम्नलिखित कायम रहे:

1. (आकार-कम) के लिए $1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0.5$. परिभाषा के अनुसार, यह संपत्ति आदेशित आधार की लंबाई में कमी की गारंटी देती है।
2. (लोवेज़ स्थिति) k = 2,3,..,n के लिए $\colon \delta \Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}\leq \Vert \mathbf {b} _{k}^{*}\Vert ^{2}+\mu _{k,k-1}^{2}\Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}$.

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

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

अनुप्रयोग

एलएलएल एल्गोरिथ्म का एक प्रारंभिक सफल अनुप्रयोग एंड्रयू ओडलीज़्को और रीले में हरमन द्वारा मर्टेंस अनुमान अनुमान को खारिज करने में इसका उपयोग था। एलएलएल एल्गोरिदम को एमआईएमओ डिटेक्शन एल्गोरिदम में कई अन्य अनुप्रयोग मिले हैं और सार्वजनिक-कुंजी एन्क्रिप्शन योजनाओं का क्रिप्टो विश्लेषण: नैकाचे-स्टर्न नैपसैक क्रिप्टोसिस्टम, विशेष सेटिंग्स के साथ आरएसए (एल्गोरिदम), एनटीआरयूएन्क्रिप्ट, इत्यादि। एल्गोरिदम का उपयोग कई समस्याओं के पूर्णांक समाधान खोजने के लिए किया जा सकता है। विशेष रूप से, एलएलएल एल्गोरिदम पूर्णांक संबंध एल्गोरिदम में से एक का मूल बनाता है। उदाहरण के लिए, यदि यह माना जाता है कि r=1.618034 पूर्णांक गुणांक वाले अज्ञात द्विघात समीकरण के लिए एक फ़ंक्शन का (थोड़ा गोलाकार) मूल है, तो कोई जाली में एलएलएल कटौती लागू कर सकता है $\mathbf {Z} ^{4}$ द्वारा फैलाया गया $[1,0,0,10000r^{2}],[0,1,0,10000r],$ और $[0,0,1,10000]$. घटे हुए आधार में पहला वेक्टर इन तीनों का एक पूर्णांक रैखिक संयोजन होगा, इस प्रकार आवश्यक रूप से $[a,b,c,10000(ar^{2}+br+c)]$; लेकिन ऐसा वेक्टर केवल तभी छोटा होता है जब a, b, c छोटे हों और $ar^{2}+br+c$ और भी छोटा है. इस प्रकार इस लघु वेक्टर की पहली तीन प्रविष्टियाँ अभिन्न द्विघात बहुपद के गुणांक होने की संभावना है जिसका मूल r है। इस उदाहरण में एलएलएल एल्गोरिदम सबसे छोटा वेक्टर पाता है [1, -1, -1, 0.00025] और वास्तव में $x^{2}-x-1$ इसका मूल स्वर्णिम अनुपात के बराबर है, 1.6180339887....

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

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

1. आधार में पहला वेक्टर लैटिस समस्या से बहुत बड़ा नहीं हो सकता # सबसे छोटा वेक्टर समस्या (एसवीपी) | सबसे छोटा गैर-शून्य वेक्टर: $\Vert \mathbf {b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{n-1}\cdot \lambda _{1}({\mathcal {L}})$. विशेष रूप से, के लिए $\delta =3/4$, यह देता है $\Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/2}\cdot \lambda _{1}({\mathcal {L}})$.
2. आधार में पहला वेक्टर भी जाली के निर्धारक से घिरा है: $\Vert \mathbf {b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{(n-1)/2}\cdot (\det({\mathcal {L}}))^{1/n}$. विशेष रूप से, के लिए $\delta =3/4$, यह देता है $\Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}$.
3. आधार में वैक्टर के मानदंडों का उत्पाद जाली के निर्धारक से बहुत बड़ा नहीं हो सकता: चलो $\delta =3/4$, तब ${\textstyle \prod _{i=1}^{n}\Vert \mathbf {b} _{i}\Vert \leq 2^{n(n-1)/4}\cdot \det({\mathcal {L}})}$.

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

निम्नलिखित विवरण पर आधारित है (Hoffstein, Pipher & Silverman 2008, Theorem 6.68), इरेटा से सुधार के साथ।

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,j⌉bj;
               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 से उदाहरण³

चलो एक जाली आधार $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in \mathbf {Z} ^{3}$, के कॉलम द्वारा दिया जाए

$${\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}$$

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

$${\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}},$$

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

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

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

$${\begin{bmatrix}-2+2i&7+3i&7+3i&-5+4i\\3+3i&-2+4i&6+2i&-1+4i\\2+2i&-8+0i&-9+1i&-7+5i\\8+2i&-9+0i&6+3i&-4+4i\end{bmatrix}},$$

तो नीचे मैट्रिक्स के कॉलम एलएलएल-कम आधार देते हैं।

$${\begin{bmatrix}-6+3i&-2+2i&2-2i&-3+6i\\6-1i&3+3i&5-5i&2+1i\\2-2i&2+2i&-3-1i&-5+3i\\-2+1i&8+2i&7+1i&-2-4i\\\end{bmatrix}}.$$

कार्यान्वयन

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

• अरागेली फ़ंक्शन के रूप में lll_reduction_int
• fpLLL एक स्टैंड-अलोन कार्यान्वयन के रूप में
• कार्यक्रम के रूप में संख्या सिद्धांत के लिए फास्ट लाइब्रेरी fmpz_lll
• फ़ंक्शन के रूप में GAP कंप्यूटर बीजगणित प्रणाली LLLReducedBasis
• खुश फ़ंक्शन के रूप में LLL पैकेज में LLLBases
• मैग्मा कंप्यूटर बीजगणित प्रणाली के कार्य LLL और LLLGram (ग्राम मैट्रिक्स लेते हुए)
• मेपल कंप्यूटर बीजगणित प्रणाली फ़ंक्शन के रूप में IntegerRelations[LLL]
• फ़ंक्शन के रूप में गणित LatticeReduce
• नंबर थ्योरी लाइब्रेरी (NTL) फ़ंक्शन के रूप में LLL
• कार्यक्रम के रूप में PARI/GP qflll
• Pymatgen फ़ंक्शन के रूप में analysis.get_lll_reduced_lattice
• विधि के रूप में सेजमैथ LLL एफपीएलएलएल और एनटीएल द्वारा संचालित
• इसाबेल/एचओएल 'औपचारिक साक्ष्यों के संग्रह' प्रविष्टि में LLL_Basis_Reduction. यह कोड कुशलतापूर्वक निष्पादन योग्य हास्केल को निर्यात करता है।

यह भी देखें

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

संदर्भ

• Napias, Huguette (1996). "A generalization of the LLL algorithm over euclidean rings or orders". Journal de Théorie des Nombres de Bordeaux. 8 (2): 387–396. doi:10.5802/jtnb.176.
• Cohen, Henri (2000). A course in computational algebraic number theory. GTM. Vol. 138. Springer. ISBN 3-540-55640-0.
• Borwein, Peter (2002). Computational Excursions in Analysis and Number Theory. ISBN 0-387-95444-9.
• Luk, Franklin T.; Qiao, Sanzheng (2011). "A pivoted LLL algorithm". Linear Algebra and Its Applications. 434 (11): 2296–2307. doi:10.1016/j.laa.2010.04.003.
• Hoffstein, Jeffrey; Pipher, Jill; Silverman, J.H. (2008). An Introduction to Mathematical Cryptography. Springer. ISBN 978-0-387-77993-5.