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

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

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

जहाँ $B$ की सबसे बड़ी लंबाई है $\mathbf {b} _{i}$ यूक्लिडियन मानदंड के अंतर्गत, अर्थात, $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}})}$.

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

निम्नलिखित विवरण पर आधारित है (हॉफस्टीन, पिफर & सिल्वरमैन 2008, प्रमेय 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.