Lenstra-Lenstra-Lovas-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 19. maaliskuuta 2020 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Lenstra-Lenstra-Lovas- algoritmi ( LLL-algoritmi , LLL-algoritmi ) on Arjen Lenstran , Hendrik Lenstran ja Laszlo Lovasin vuonna 1982 kehittämä hilapohjainen pelkistysalgoritmi 1] . Polynomiajassa algoritmi muuntaa hilassa olevan kannan (alaryhmä ) lyhimmäksi lähes ortogonaaliksi kantaksi samassa hilassa. Vuodesta 2019 lähtien Lenstra-Lenstra-Lovas-algoritmi on yksi tehokkaimmista laskettaessa pelkistettyä kantaa korkeadimensionaalisissa hilassa . Sillä on merkitystä ensisijaisesti ongelmissa, jotka rajoittuvat lyhimmän hilavektorin löytämiseen . $\mathbb {R} ^{n}$

Historia

Algoritmin kehittivät hollantilaiset matemaatikot Arjen Lenstra ja Hendrik Lenstra yhdessä unkarilaisen matemaatikon Laszlo Lovasin kanssa vuonna 1982 [1] [2] .

Pääedellytys LLL-algoritmin luomiselle oli, että Gram–Schmidt-prosessi toimii vain vektoreiden kanssa, joiden komponentit ovat reaalilukuja . Vektoriavaruudelle Gram – Schmidt-prosessi mahdollistaa mielivaltaisen kannan muuntamisen ortonormaaliksi ( " ideaaliksi", johon LLL-algoritmi pyrkii). Mutta Gram-Schmidt-prosessi ei takaa, että lähdössä jokainen vektoreista on alkuperäisen perustan lineaarinen kokonaislukuyhdistelmä . Näin ollen tuloksena oleva vektoreiden joukko ei välttämättä ole alkuperäisen hilan perusta. Tämä johti tarpeeseen luoda erityinen algoritmi hilatyöskentelyä varten [3] . $\mathbb {R} ^{n}$

Aluksi algoritmia käytettiin polynomien tekijöihin jakamiseen kokonaislukukertoimilla , reaalilukujen diofantiiniapproksimaatioiden laskemiseen ja lineaarisen ohjelmoinnin ongelmien ratkaisemiseen kiinteäulotteisissa avaruudessa ja myöhemmin kryptausanalyysissä [4] [2] .

Perusalennus

Euklidisen avaruuden hila on lineaarisesti riippumattomien vektorien muodostaman ryhmän alaryhmä , jota kutsutaan hilan kantaksi. Mikä tahansa hilavektori voidaan esittää perusvektoreiden lineaarisella kokonaislukuyhdistelmällä [5] . Hilan kanta määritellään moniselitteisesti: kuva esittää saman hilan kaksi eri kantaa. $(\mathbb {R} ^{n},+)$ $d$ $\mathbb {R} ^{n}$

Kantavähennys koostuu hilapohjan saamisesta erityiseen muotoon, joka tyydyttää tietyt ominaisuudet. Supistetun kantaluvun tulee olla mahdollisuuksien mukaan lyhin hilan kantajista ja lähellä ortogonaalista (mikä ilmaistaan siinä, että lopulliset Gram-Schmidt-kertoimet eivät saa olla suurempia kuin ) [3] . $1/2$

Saavutetaan Gram-Schmidt-prosessilla tehdyn kannan muunnoksen tuloksena kanta , jonka Gram-Schmidt-kertoimet määritellään seuraavasti: $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b } _{d}^{*}\}$

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

, kaikille sellaisille .

{\näyttötyyli j,i}

1\leqslant j<i\leqslant d

Sitten (järjestettyä) kantaa kutsutaan -LLL-vähennetyksi kantaksi (missä parametri on välissä ), jos se täyttää seuraavat ominaisuudet [3] : $\mathbf {B}$ $\delta$ $\delta$ ${\textstyle (0.25,1]}$

Kaikille sellaisille . (vähennysehto) $i, j$ $1\leqslant j<i\leqslant d\colon \left|\mu _{i,j}\right|\leqslant 0{,}5$
Pitoon : . (Lovaksen kunto) ${\näyttötyyli k=1,2,\pisteet ,d}$ $(\delta -\mu _{k,k-1}^{2})\|\mathbf {b} _{k-1}^{*}\|^{2}\leqslant \|\ mathbf {b} _{k}^{*}\|^{2}$

Tässä on vektorin normi , on vektorien skalaaritulo . $\|\mathbf {b} \|$ $\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle$

Aluksi Lenstra, Lenstra ja Lovas esittelivät artikkelissaan parametrin algoritmin toiminnan . Vaikka algoritmi pysyy oikeana , sen polynomiaikainen toiminta on taattu vain välissä [1] . ${\textstyle \delta ={\frac {3}{4}}}$ $\delta=1$ $\delta$ $(0.25,1)$

Vähennetyt perusominaisuudet

Olkoon pohja LLL-algoritmilla vähennetylle hilalle parametrilla . Tällaisen perustan määritelmästä voidaan johtaa useita ominaisuuksia . Olkoon lyhimmän hilavektorin normi , niin: $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $\delta$ ${\mathcal L}$ $\mathbf {B}$ $\lambda _{1}({\mathcal {L}})$

Ensimmäinen kantavektori ei voi olla merkittävästi pidempi kuin lyhin nollasta poikkeava vektori : ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\right)^{d-1}\cdot \lambda _{1}({\mathcal {L}})}$ . Erityisesti, sillä käy ilmi [6] . $\delta =3/4$ $\|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/2}\cdot \lambda _{1}({\mathcal {L)))$
Ensimmäistä kantavektoria rajoittaa hiladeterminantti : ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\oikea)^{(d-1)/ 2}\cdot \det({\mathcal {L}})^{1/d}}$ . Erityisesti, sillä käy ilmi [3] . $\delta =3/4$ ${\displaystyle \|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/4}\cdot (\det {\mathcal {L)))^{1/d))$
Vektorinormien tulo ei voi olla paljon suurempi kuin hilan determinantti: ${\textstyle \prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1)) }\oikea)^{d(d-1)/2}\cdot \det({\mathcal {L)))}$ . Erityisesti [ 3 ] . $\prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant 2^{d(d-1)/4}\cdot \det({\mathcal {L)))$ $\delta =3/4$

LLL-menetelmällä muunnettu kanta on lähes lyhin mahdollinen siinä mielessä, että on olemassa absoluuttiset rajat , jolloin ensimmäinen kantavektori on enintään kertaa niin pitkä kuin lyhin hilavektori, samoin toinen kantavektori on enintään toiseksi lyhimmän hilavektorin tekijä ja niin edelleen (joka seuraa suoraan ominaisuudesta 1) [6] . $c_{i}>1$ $c_{1}$ $c_{2}$

Algoritmi

Syöte [7] :

hilakanta (koostuu lineaarisesti riippumattomista vektoreista),

{\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\in \displaystyle \mathbb {R} ^{3))

parametri c , useimmiten (parametrin valinta riippuu tietystä tehtävästä).

\delta

{\textstyle {\frac {1}{4}}<\delta <1}

{\textstyle \delta ={\frac {3}{4}}}

Toimintojen järjestys [4] :

Ensin luodaan kopio alkuperäisestä kannasta, joka ortogonalisoidaan siten, että algoritmin aikana nykyistä kantaa verrataan tuloksena olevaan kopioon ortogonaalisuuden suhteen ( ). $\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{d}^{*}$
Jos mikä tahansa Gram-Schmidt-kerroin (c ) on itseisarvoltaan suurempi kuin , niin yhden nykyisen kannan vektoreista projektio ortogonalisoidun kannan vektoriin, jolla on eri luku, on yli puolet . Tämä tarkoittaa, että vektorista on vähennettävä vektori kerrottuna pyöristetyllä (pyöristys on tarpeen, koska hilavektori pysyy saman hilan vektorina vain kerrottuna kokonaisluvulla, mikä seuraa sen määritelmästä). Sitten se pienenee , koska nyt projektio on alle puolet . Näin ollen tarkistetaan LLL-vähennetyn perusteen määritelmän ensimmäisen ehdon noudattaminen. $\vert \mu _{k,j}\vert$ $j<k$ $0{,}5$ ${\displaystyle \mathbf {b} _{k))$ $\mathbf {b} _{j}^{*}$ $\mathbf {b} _{j}^{*}$ ${\displaystyle \mathbf {b} _{k))$ ${\mathbf {b}}_{j}$ $\vert \mu _{k,j}\vert$ $\vert \mu _{k,j}\vert$ $0{,}5$ ${\displaystyle \mathbf {b} _{k))$ $\mathbf {b} _{j}^{*}$ $\mathbf {b} _{j}^{*}$
Laskettu uudelleen . ${\displaystyle \mu _{k,j))$ $j<k$
Kohdalle , tarkistetaan 2. ehto, jonka algoritmin kirjoittajat ovat esittäneet LLL-vähennetyn perustan määritelmänä [1] . Jos ehto ei täyty, tarkistettujen vektorien indeksit vaihdetaan. Ja ehto tarkistetaan uudelleen samalle vektorille (jo uudella indeksillä). ${\displaystyle \mathbf {b} _{k))$
Laskettu uudelleen puolesta ja puolesta $\mathbf {b} _{k}^{*},\mathbf {b} _{k-1}^{*},\langle \mathbf {b} _{k}^{*},\ mathbf {b} _{k}^{*}\rangle ,\langle \mathbf {b} _{k-1}^{*},\mathbf {b} _{k-1}^{*}\rangle$ $k>1$ ${\displaystyle \mu _{k-1,j},\mu _{k,j))$ $j<k$
Jos jäljellä on ylittäviä absoluuttisia arvoja (jo toisen kanssa ), meidän on palattava kohtaan 2. ${\displaystyle \mu _{k,j))$ $0{,}5$ $k$
Kun kaikki ehdot on tarkistettu ja muutoksia on tehty, algoritmi päättyy.

Algoritmissa - pyöristys matematiikan sääntöjen mukaan. Algoritmin prosessi, joka on kuvattu pseudokoodissa [7] : $\lfloor \mu _{k,j}\rceil$

orto

:=\mathrm {gramSchmidt} (\{\mathbf {b} _{1},\dots ,\mathbf {b} _{d}\})=\{\mathbf {b} _{1} ^{*},\dots ,\mathbf {b} _{d}^{*}\}

(suorita Gram-Schmidt-prosessi ilman normalisointia); määrittää ,

{\textstyle \mu _{k,j}:={\frac {\langle \mathbf {b} _{k},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}}

aina viimeisimpien tähän mennessä osoitettujen arvojen

\mathbf {b} _{k},\mathbf {b} _{j}^{*}

mukaan : j : lle arvosta 0 :aan : jos , sitten : ; Päivitä arvotkohteelle; lopputila ; _ syklin loppu ; jos , niin : else : swap ja paikat; Päivitä arvotkohteelle; varten; ; lopputila ; _ syklin loppu .

k = 2

k\leqslant d

k-1

{\textstyle |\mu _{k,j}|>{\frac {1}{2))}

{\displaystyle \mathbf {b} _{k}=\mathbf {b} _{k}-\lfloor \mu _{k,j}\rceil \mathbf {b} _{j))

|\mu _{k,j}|

j<k

{\textstyle (\delta -\mu _{k,k-1}^{2})\|\mathbf {b} _{k-1}^{*}\|^{2}\leqslant \|\ mathbf {b} _{k}^{*}\|^{2}}

k=k+1

{\displaystyle \mathbf {b} _{k))

\mathbf {b} _{k-1}

\mathbf {b} _{k}^{*},\mathbf {b} _{k-1}^{*},\langle \mathbf {b} _{k}^{*},\ mathbf {b} _{k}^{*}\rangle ,\langle \mathbf {b} _{k-1}^{*},\mathbf {b} _{k-1}^{*}\rangle

k>1

{\displaystyle \mu _{k-1,j},\mu _{k,j))

j<k

k=\max(k-1,1)

Lähtötiedot: alennettu peruste: . ${\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d))$

Laskennallinen monimutkaisuus

Syöte sisältää -ulotteisten vektorien perustan , jossa on . $n$ $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $\ d\leqslant n$

Jos kantavektorit koostuvat kokonaislukukomponenteista, algoritmi approkimoi lyhimmän lähes ortogonaalisen kantaosan polynomiajassa , jossa on maksimipituus euklidisessa normissa eli . LLL-algoritmin pääsilmukka vaatii iteraatioita ja toimii pituisilla numeroilla . Koska pituusvektorit käsitellään jokaisessa iteraatiossa , algoritmi vaatii aritmeettisia operaatioita. Naiivien algoritmien käyttö kokonaislukujen yhteen- ja kertolaskussa johtaa bittikohtaisiin operaatioihin [3] . $O(d^{5}n\log ^{3}B)$ $B$ ${\mathbf {b}}_{i}$ $B=\max \left(\|\mathbf {b} _{1}\|_{2},\|\mathbf {b} _{2}\|_{2},..., \|\mathbf {b} _{d}\|_{2}\right)$ $O(d^{2}\log B)$ $O(d\log B)$ $d$ $n$ $O(d^{3}n\log ^{3}B)$ $O(d^{5}n\log ^{3}B)$

Siinä tapauksessa, että hilassa on rationaalisia komponentteja sisältävä kanta, nämä rationaaliset luvut on ensin muutettava kokonaisluvuiksi kertomalla kantavektorit niiden komponenttien nimittäjillä (nimittäjien joukko on rajoitettu johonkin kokonaislukuun ). Mutta silloin operaatiot suoritetaan jo kokonaisluvuille, jotka eivät ylitä . Tämän seurauksena bittitoimintoja on maksimissaan . Siinä tapauksessa, että hila on annettu muodossa , algoritmin monimutkaisuus pysyy samana, mutta bittioperaatioiden määrä kasvaa. Koska tietokoneesituksessa mikä tahansa reaaliluku korvataan rationaalisella bittiesityksen rajoittuneisuudesta johtuen, tuloksena oleva estimaatti pätee myös todellisille hiloille [3] . $X$ $X^{nd}$ $O(d^{8}n^{4}\log ^{3}X)$ $\mathbb {R} ^{n}$

Samanaikaisesti alle 4:n dimensioissa kantavähennysongelma ratkaistaan tehokkaammin Lagrange-algoritmilla [8] .

Esimerkki

Wib Bosman [9] antama esimerkki .

Olkoon hilan kanta (alaryhmänä ) matriisin sarakkeiden avulla: $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in \displaystyle \mathbb {Z} ^{3}$ $(\mathbb {R} ^{n},+)$

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

Algoritmin aikana saadaan seuraavaa:

Gram-Schmidtin ortogonalisointiprosessi
1. ${\textstyle b_{1}^{*}=b_{1}={\begin{bmatrix}1\\1\\1\end{bmatrix)),B_{1}=\langle b_{1}^{ *},b_{1}^{*}\rangle =3}$
2. ${\textstyle \mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1))}={\frac {1}{3 }}\left(<{\frac {1}{2}}\right)}$ , ja $b_{2}^{*}=b_{2}-\mu _{2,1}b_{1}^{*}={\begin{bmatrix}{\frac {-4}{3} }\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatrix}}$ ${\textstyle B_{2}=\langle b_{2}^{*},b_{2}^{*}\rangle ={\frac {14}{3)).}$
3. ${\textstyle \mu _{3,1}={\frac {14}{3}}(>{\frac {1}{2}})}$ , siksi ja , sitten ja $b_{3}^{*}={\begin{bmatrix}{\frac {-5}{3}}\\{\frac {1}{3}}\\{\frac {4}{ 3}}\end{bmatrix}}}$ ${\textstyle \mu _{3,2}={\frac {\langle b_{3},b_{2}^{*}\rangle }{B_{2))}={\frac {13}{14 }}\left(>{\frac {1}{2}}\right)}$ ${\textstyle b_{3}^{*}={\begin{bmatrix}{\frac {-6}{14}}\\{\frac {9}{14}}\\{\frac {-3} {14}}\end{bmatrix}}}$ ${\textstyle B_{3}={\frac {9}{14}}}$
Sillä meillä on ja , joten siirrymme seuraavaan vaiheeseen. $k = 2$ $\mu _{2,1}<{\frac {1}{2}}$ $(\delta -\mu _{2,1}^{2})\|\mathbf {b} _{1}^{*}\|^{2}\leqslant \|\mathbf {b} _{2}^{*}\|^{2}$
Kun meillä on: $k = 3$
1. $\lfloor \mu _{3,2}\rceil =1$ tarkoittaa nyt ${\textstyle b_{3}=b_{3}-1\cdot b_{2}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\begin{bmatrix}-1\ \0\\2\end{bmatrix}}={\begin{bmatrix}4\\5\\4\end{bmatrix}}}$ ${\textstyle \mu _{3,2}={\frac {13}{14}}-1=-{\frac {1}{14}},\mu _{3,1}={\frac { 13}{3}}}$
2. $\lfloor \mu _{3,1}\rceil =4$ tarkoittaa nyt ${\textstyle b_{3}=b_{3}-4\cdot b_{1}={\begin{bmatrix}4\\5\\4\end{bmatrix}}-{\begin{bmatrix}4\\ 4\\4\end{bmatrix}}={\begin{bmatrix}0\\1\\0\end{bmatrix}}}$ ${\textstyle \mu _{3,2}=-{\frac {1}{14)),\mu _{3,1}={\frac {1}{3))}$
3. $(\delta -\mu _{3,2}^{2})\|\mathbf {b} _{2}^{*}\|^{2}>\|\mathbf {b} _ {3}^{*}\|^{2}$ , joten he vaihtavat paikkaa. $b_{3}$ $b_{2}$
Nyt palataan vaiheeseen 1, kun välimatriisilla on muoto $(\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3})$ ${\begin{bmatrix}1&0&-1\\1&1&0\\1&0&2\end{bmatrix}}$

Lähtötiedot: Lenstra-Lenstra-Lovas-menetelmällä vähennetty peruste:

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

Sovellus

Algoritmia käytetään usein MIMO -menetelmässä (Spatial Sign Coding) useiden antennien vastaanottamien signaalien dekoodaamiseen [10] ja julkisen avaimen salausjärjestelmissä : selkäreppuongelmaan perustuvat salausjärjestelmät , RSA tietyillä asetuksilla, NTRUEncrypt ja niin edelleen . Algoritmin avulla voidaan löytää kokonaislukuratkaisuja lukuisissa lukuteorian ongelmissa, erityisesti polynomin juuria kokonaislukuina [11] .

Julkisen avaimen salausjärjestelmiin ( NTRU ) kohdistuvissa hyökkäyksissä algoritmia käytetään lyhimmän hilavektorin löytämiseen, koska algoritmi löytää lopulta kokonaisen joukon lyhimpiä vektoreita [12] .

RSA-kryptausanalyysissä pienellä CRT-eksponentilla tehtävä, kuten NTRU:n tapauksessa, pelkistetään lyhimmän hilan kantavektorin löytämiseen, joka löytyy polynomiajassa (kantadimensioista) [13] .

Selkäreppuongelmissa, erityisesti hyökätäkseen Merkle-Hellmanin salausjärjestelmään, LLL-algoritmi etsii supistettua hilapohjaa [14] .

Muunnelmia ja yleistyksiä

Liukulukuaritmeettinen käyttö rationaalisten lukujen tarkan esityksen sijaan voi nopeuttaa LLL-algoritmia merkittävästi hyvin pienten numeeristen virheiden kustannuksella [15] .

Algoritmin toteutukset

Ohjelmallisesti algoritmi toteutetaan seuraavassa ohjelmistossa:

fpLLL : ssä itsenäisenä toteutuksena [16] ;
GAP : ssa funktiona LLLReducedBasis [17] ;
Macaulay2 : ssa funktiona LLLkirjastossa LLLBases [18] ;
Magmassa [ molemmat funktiot LLLja LLLGram [19] ;
Maplessa funktiona [ 20 IntegerRelations[LLL] ] ;
Mathematicassa funktiona LatticeReduce [21 ] ;
Numeroteoriakirjastossa (NTL) moduulina LLL [22] ;
PARI/GP : ssä funktiona qflll [23] ;
Pymatgenissa funktiona [ 24 analysis.get_lll_reduced_lattice ] ;
SageMathissa fpLLLLLL :ssä ja NTL:ssä toteutettu menetelmä [25] .

Muistiinpanot

↑ 1 2 3 4 A. K. Lenstra, H. W. Lenstra Jr., L. Lovász. Polynomien faktorointi rationaalisilla kertoimilla // Mathematische Annalen . - 1982. - S. 515-534 . — ISSN 4 . - doi : 10.1007/BF01457454 .
↑ 1 2 LLL-algoritmi, 2010 , 1 LLL-algoritmin historia.
↑ 1 2 3 4 5 6 7 Galbraith, Steven. 17. Lattice Reduction // Mathematics of Public Key Cryptography (englanti) . - 2012. Arkistoitu 20. syyskuuta 2015 Wayback Machineen
↑ 1 2 Xinyue, Deng. Johdatus LLL-algoritmiin // Massachusetts Institute of Technology. - s. 9-10 . Arkistoitu alkuperäisestä 8. joulukuuta 2019.
↑ Cherednik I. V. Ei-negatiivinen hilapohja // 3. painos. – Diskreetti. Mat., 2014. - T. 26 . - S. 127-135 . (Venäjän kieli)
↑ 1 2 Regev, Oded. Tietojenkäsittelytieteen hilat: LLL-algoritmi // New Yorkin yliopisto. Arkistoitu alkuperäisestä 20. maaliskuuta 2021.
↑ 1 2 Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH Johdatus matemaattiseen kryptografiaan . - Springer, 2008. - s. 411. - ISBN 978-0-387-77993-5 .
↑ Nguyen, Phong Q., Stehlé, Damien. Mataladimensioinen hilapohjainen vähennys tarkistettu // ACM Transactions on Algorithms. - s. 1-48 . - doi : 10.1145/1597036.1597050 .
↑ Bosma, Wieb. 4. LLL // Tietokonealgebra. - 2007. Arkistoitu 8. toukokuuta 2019.
↑ Shahriar Shahabuddin, Janne Janhunen, Zaheer Khan, Markku Juntti, Amanullah Ghazi. Mukautettu hilavähennysmoniprosessori MIMO-tunnistusta varten // 2015 IEEE International Symposium on Circuits and Systems (ISCAS). - 2015. - arXiv : 1501.04860 . - doi : 10.1109/ISCAS.2015.7169312 .
↑ D. Simon. Valitut LLL:n sovellukset lukuteoriassa // LLL+25 Conference. - Caen, Ranska. Arkistoitu 6. toukokuuta 2021.
↑ Abderrahmane, Nitaj. NTRU:n krypta-analyysi kahdella julkisella avaimella // International Association for Cryptologic Research. - Caen, Ranska. Arkistoitu alkuperäisestä 21. joulukuuta 2019.
↑ Bleichenbacher, Daniel ja May, Alexander. Uusia hyökkäyksiä RSA:ta vastaan pienillä salaisilla CRT-eksponenteilla // International Association for Cryptologic Research. - Darmstadt, Saksa. Arkistoitu alkuperäisestä 24. kesäkuuta 2021.
↑ Liu, Jiayang, Bi, Jingguo ja Xu, Songyan. Parannettu hyökkäys Merkle–Hellmanin selkäreppujen salausjärjestelmiin // IEEE. - Beijing 100084, Kiina. Arkistoitu alkuperäisestä 17. kesäkuuta 2021.
↑ LLL-algoritmi, 2010 , 4 LLL:n ja hilan vähentämisen edistyminen.
↑ FPLLL-kehitystiimi. FPLLL, hilavähennyskirjasto . — 2016. Arkistoitu 17. helmikuuta 2020.
↑ Integraalimatriisit ja hilat . GAP . Haettu 10. joulukuuta 2019. Arkistoitu alkuperäisestä 19. joulukuuta 2019. (määrätön)
↑ LLLBases -- hilavähennys (Lenstra-Lenstra-Lovasz-emäkset) . Macaulay2 . Haettu 10. joulukuuta 2019. Arkistoitu alkuperäisestä 10. joulukuuta 2019. (määrätön)
↑ LLL-vähennys . Magma . Haettu 10. joulukuuta 2019. Arkistoitu alkuperäisestä 10. joulukuuta 2019. (määrätön)
↑ IntegerRelations/LLL . vaahtera . Haettu 10. joulukuuta 2019. Arkistoitu alkuperäisestä 18. syyskuuta 2020. (määrätön)
↑ LatticeReduce . Wolfram-kielidokumentaatio . Haettu 10. joulukuuta 2019. Arkistoitu alkuperäisestä 10. joulukuuta 2019. (määrätön)
↑ MODUULI:LLL . NTL . Haettu 10. joulukuuta 2019. Arkistoitu alkuperäisestä 17. elokuuta 2018. (määrätön)
↑ Vektorit, matriisit, lineaarialgebra ja joukot . PARI/GP . Haettu 10. joulukuuta 2019. Arkistoitu alkuperäisestä 18. joulukuuta 2019. (määrätön)
↑ pymatgen.core.lattice -moduuli . pymatgen . Haettu 27. joulukuuta 2019. Arkistoitu alkuperäisestä 18. joulukuuta 2019. (määrätön)
↑ Tiheät matriisit kokonaislukurenkaan päällä . salvia . Haettu 18. joulukuuta 2019. Arkistoitu alkuperäisestä 6. toukokuuta 2021. (määrätön)

Kirjallisuus

Huguette, Napias. LLL-algoritmin yleistys euklidisten renkaiden tai järjestysten yli // J. The. Nombr. Bordeaux. - 1996. - doi : 10.5802/jtnb.176 .
Cohen, Henry. Laskennallisen algebrallisen lukuteorian kurssi (englanniksi) . - Springer, 2000. - Voi. 138. - (GTM). — ISBN 3-540-55640-0 .
Borwein, Peter. Laskennalliset retket analyysissä ja lukuteoriassa . - 2002. - ISBN 0-387-95444-9 .
Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH Johdatus matemaattiseen kryptografiaan . - Springer, 2008. - ISBN 978-0-387-77993-5 .
Luk, Franklin T.; Qiao, Sanzheng. Kierretty LLL-algoritmi // Lin. Alg. Appl.. - 2011. - T. 434 , nro 11 . - S. 2296-2307 . - doi : 10.1016/j.laa.2010.04.003 .
LLL-algoritmi: Tutkimus ja sovellukset / Ed. kirjoittaneet Phong Q. Nguyen ja Brigitte Vallee. - Springer, 2010. - ISBN 978-3-642-02295-1 . - doi : 10.1007/978-3-642-02295-1 .
Murray R. Bremner. Lattice Basis Reduction: Johdatus LLL-algoritmiin ja sen sovelluksiin. - CRC Press, 2011. - ISBN 9781439807026 .

Lukuteoreettiset algoritmit
Yksinkertaisuustestit	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saksi Nightingale - Strassen
Alkulukujen löytäminen	Iterointi jakajien yli Eratosthenesin seula Atkinin seula Seula Sundarama
Faktorisointi	Iterointi jakajien yli Fermat menetelmä p −1 Pollardin menetelmä Pollardin ρ-algoritmi Lehmannin menetelmä Elliptisen käyrän menetelmä (Lenstran algoritmi) Dixonin algoritmi Neliömäinen seula
Diskreetti logaritmi	Gelfond-Shanks -algoritmi Polig-Hellman-algoritmi Pollardin ρ-menetelmä Pollardin kenguru-algoritmi Adlemanin algoritmi COS-algoritmi
GCD:n löytäminen	Eukleideen algoritmi Kehittynyt algoritmi Binäärinen algoritmi
Modulo-aritmetiikka	Montgomeryn algoritmi Kiinan jäännöslause
Lukujen kerto- ja jakolasku	Karatsuba-algoritmi Toom-Cook-algoritmi Schönhage-Strassen-algoritmi Fuhrer-algoritmi Harvey-van der Hoeven-algoritmi Burnickel-Ziegler-algoritmi
Neliöjuuren laskeminen	Tonelli-Shanks-algoritmi Berlekamp-Rabin-algoritmi