Lenstra-Lenstra-Lovas algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 19 mars 2020; kontroller kräver 3 redigeringar .

Lenstra-Lenstra-Lovas- algoritmen ( LLL-algorithm , LLL-algorithm ) är en gitterbasreduktionsalgoritm [ utvecklad av Arjen Lenstra , Hendrik Lenstra och Laszlo Lovas 1982 [ 1] . I polynomtid omvandlar algoritmen en bas på ett gitter (undergrupp ) till den kortaste nästan ortogonala basen på samma gitter. Från och med 2019 är Lenstra-Lenstra-Lovas-algoritmen en av de mest effektiva för att beräkna den reducerade basen i högdimensionella gitter . Det är främst relevant i problem som reducerar till att hitta den kortaste gittervektorn . $\mathbb {R} ^{n}$

Historik

Algoritmen utvecklades av de holländska matematikerna Arjen Lenstra och Hendrik Lenstra tillsammans med den ungerske matematikern Laszlo Lovas 1982 [1] [2] .

Huvudförutsättningen för skapandet av LLL-algoritmen var att Gram-Schmidt-processen endast fungerar med vektorer vars komponenter är reella tal . För ett vektorrum gör Gram–Schmidt-processen det möjligt att omvandla en godtycklig bas till en ortonormal (“ideal”, som LLL-algoritmen tenderar mot). Men Gram-Schmidt-processen garanterar inte att var och en av vektorerna vid utgången kommer att vara en heltalslinjär kombination av den ursprungliga basen. Den resulterande uppsättningen vektorer kanske inte är grunden för det ursprungliga gittret. Detta ledde till behovet av att skapa en speciell algoritm för att arbeta med gitter [3] . $\mathbb {R} ^{n}$

Ursprungligen användes algoritmen för att faktorisera polynom med heltalskoefficienter , beräkna diofantiska approximationer av reella tal och för att lösa linjära programmeringsproblem i fastdimensionella utrymmen , och senare för kryptoanalys [4] [2] .

Grundreduktion

Ett gitter i det euklidiska utrymmet är en undergrupp av gruppen som genereras av linjärt oberoende vektorer från , kallad basen för gittret. Vilken gittervektor som helst kan representeras av en heltalslinjär kombination av basvektorer [5] . Grunden för ett gitter definieras tvetydigt: figuren visar två olika baser av samma gitter. $(\mathbb {R} ^{n},+)$ $d$ $\mathbb {R} ^{n}$

Basreduktion består i att bringa gitterunderlaget till en speciell form som uppfyller vissa egenskaper. Den reducerade basen bör om möjligt vara den kortaste bland alla baser i gittret och nära ortogonal (vilket uttrycks i det faktum att de slutliga Gram-Schmidt-koefficienterna inte bör vara mer än ) [3] . $1/2$

Låt, som ett resultat av omvandlingen av basen med hjälp av Gram-Schmidt-processen , basen , med Gram-Schmidt-koefficienterna definierade enligt följande, erhållas: $\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 }}}

, för allt sådant .

j,i

1\leqslant j<i\leqslant d

Då kallas en (ordnad) bas en -LLL-reducerad bas (där parametern är i intervallet ) om den uppfyller följande egenskaper [3] : $\mathbf {B}$ $\delta$ $\delta$ ${\textstyle (0.25,1]}$

För allt sådant . (reduktionsvillkor) $I j$ $1\leqslant j<i\leqslant d\colon \left|\mu _{i,j}\right|\leqslant 0{,}5$
För lastrum: . (Lovas skick) $k=1,2,\dots ,d$ $(\delta -\mu _{k,k-1}^{2})\|\mathbf {b} _{k-1}^{*}\|^{2}\leqslant \|\ mathbf {b} _{k}^{*}\|^{2}$

Här är normen för vektorn , är den skalära produkten av vektorer. $\|\mathbf {b} \|$ $\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle$

Inledningsvis demonstrerade Lenstra, Lenstra och Lovas funktionen av algoritmen för parametern i deras papper . Även om algoritmen förblir korrekt för , garanteras dess polynomtidsfunktion endast för i intervallet [1] . ${\textstil \delta ={\frac {3}{4}}}$ $\delta=1$ $\delta$ $(0.25,1)$

Reducerade basegenskaper

Låta vara en grund på gittret reducerat av LLL-algoritmen med parametern . Flera egenskaper kan härledas från definitionen av en sådan grund . Låt vara normen för den kortaste gittervektorn, då : $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $\delta$ ${\mathcal L}$ $\mathbf {B}$ $\lambda _{1}({\mathcal {L}})$

Den första basvektorn kan inte vara betydligt längre än den kortaste vektorn som inte är noll : ${\textstil \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\right)^{d-1}\cdot \lambda _{1}({\mathcal {L}})}$ . I synnerhet, för det visar sig [6] . $\delta =3/4$ $\|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/2}\cdot \lambda _{1}({\mathcal {L)))$
Den första basvektorn begränsas av gitterdeterminanten : ${\textstil \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\right)^{(d-1)/ 2}\cdot \det({\mathcal {L}})^{1/d}}$ . I synnerhet, för det visar sig [3] . $\delta =3/4$ ${\displaystyle \|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/4}\cdot (\det {\mathcal {L)))^{1/d))$
Produkten av vektornormer kan inte vara mycket större än gittrets determinant: ${\textstyle \prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1)) }\right)^{d(d-1)/2}\cdot \det({\mathcal {L)))}$ . I synnerhet för [3] . $\prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant 2^{d(d-1)/4}\cdot \det({\mathcal {L)))$ $\delta =3/4$

Basen transformerad med LLL-metoden är nästan den kortaste möjliga, i den meningen att det finns absoluta gränser så att den första basvektorn inte är mer än gånger så lång som den kortaste gittervektorn, på samma sätt är den andra basvektorn inte mer än en faktor av sekunden den kortaste gittervektorn, och så vidare (vilket direkt följer av egenskap 1) [6] . $c_{i}>1$ $c_{1}$ $c_{2}$

Algoritm

Ingång [7] :

gitterbas (består av linjärt oberoende vektorer),

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

parameter c , oftast (valet av parameter beror på den specifika uppgiften).

\delta

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

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

Åtgärdssekvens [4] :

Först skapas en kopia av originalbasen, som ortogonaliseras så att under algoritmens gång den aktuella basen jämförs med den resulterande kopian för ortogonalitet ( ). $\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{d}^{*}$
Om någon Gram-Schmidt-koefficient (c ) är större i absolut värde än , då är projektionen av en av vektorerna för den nuvarande basen på vektorn för en ortogonaliserad bas med ett annat nummer mer än hälften . Detta betyder att det är nödvändigt att subtrahera vektorn multiplicerad med den avrundade vektorn (avrundning är nödvändig, eftersom gittervektorn förblir vektorn för samma gitter endast när den multipliceras med ett heltal, vilket följer av dess definition). Då blir det mindre , eftersom nu projektionen på blir mindre än hälften . Sålunda görs en kontroll av överensstämmelse med 1:a villkoret från definitionen av ett LLL-reducerat underlag. $\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}^{*}$
Omräknat för . ${\displaystyle \mu _{k,j))$ $j<k$
För , det andra villkoret kontrolleras, introducerat av författarna till algoritmen som definitionen av en LLL-reducerad bas [1] . Om villkoret inte är uppfyllt, byts indexen för de kontrollerade vektorerna. Och villkoret kontrolleras igen för samma vektor (redan med ett nytt index). ${\displaystyle \mathbf {b} _{k))$
Omräknat för och för $\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$
Om det finns någon kvar som överskrider i absolut värde (redan med en annan ), måste vi återgå till punkt 2. ${\displaystyle \mu _{k,j))$ $0{,}5$ $k$
När alla villkor är kontrollerade och ändringar görs, avslutas algoritmen.

I algoritmen - avrundning enligt matematikens regler. Processen för algoritmen, beskriven i pseudokod [7] : $\lfloor \mu _{k,j}\rceil$

ortho

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

(utför Gram-Schmidt-processen utan normalisering); bestämma ,

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

alltid antyda de mest aktuella värdena

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

tilldela

k=2

hittills :

k\leqslant d

för j från till 0 : if , då : ; Uppdatera värdenför; slutvillkor ; _ slutet av cykeln ; om , då : annat : byta och platser; Uppdatera värdenför; för; ; slutvillkor ; _ slutet av cykeln .

k-1

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

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

|\mu _{k,j}|

j<k

{\textstil (\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)

Utdata: reducerad bas: . ${\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d))$

Beräkningskomplexitet

Ingången innehåller en bas av dimensionella vektorer med . $n$ $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $\ d\leqslant n$

Om basvektorerna består av heltalskomponenter, approximerar algoritmen den kortaste nästan ortogonala basen i polynomtid , där är den maximala längden i den euklidiska normen , dvs. Huvudslingan i LLL-algoritmen kräver iterationer och fungerar med antal längder . Eftersom längdvektorer bearbetas vid varje iteration kräver algoritmen aritmetiska operationer som ett resultat. Användningen av naiva algoritmer för addition och multiplikation av heltal resulterar i bitvisa operationer [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)$

I det fall då gittret har en bas med rationella komponenter, måste dessa rationella tal först omvandlas till heltal genom att multiplicera basvektorerna med nämnare av deras komponenter (uppsättningen av nämnare är begränsad till något heltal ). Men då kommer operationer att utföras redan på heltal som inte överstiger . Som ett resultat kommer det att finnas maximalt antal bitoperationer . För det fall då gittret anges i , förblir komplexiteten hos algoritmen densamma, men antalet bitoperationer ökar. Eftersom i datorrepresentationen vilket reellt tal som helst ersätts med ett rationellt på grund av bitrepresentationens begränsade storlek, är den resulterande uppskattningen även sann för reella gitter [3] . $X$ $X^{nd}$ $O(d^{8}n^{4}\log ^{3}X)$ $\mathbb {R} ^{n}$

Samtidigt, för dimensioner mindre än 4, löses problemet med basreduktion mer effektivt av Lagrange-algoritmen [8] .

Exempel

Ett exempel ges av Wib Bosma [9] .

Låt basen för gittret (som en undergrupp ) ges av matrisens kolumner: $\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}}

Under algoritmen erhålls följande:

Gram-Schmidts ortogonaliseringsprocess
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)}$ , och $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}})}$ , därför och , sedan och $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))}$
För vi har och , så vi går till nästa steg. $k=2$ $\mu _{2,1}<{\frac {1}{2))$ $(\delta -\mu _{2,1}^{2})\|\mathbf {b} _{1}^{*}\|^{2}\leqslant \|\mathbf {b} _{2}^{*}\|^{2}$
När vi har: $k=3$
1. $\lfloor \mu _{3,2}\rceil =1$ betyder nu ${\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}}}$ ${\textstil \mu _{3,2}={\frac {13}{14}}-1=-{\frac {1}{14}},\mu _{3,1}={\frac { 13}{3}}}$
2. $\lfloor \mu _{3,1}\rceil =4$ betyder nu ${\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}}}$ ${\textstil \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}$ , så de byter plats. ${\displaystyle b_{3))$ $b_{2}$
Nu återgår vi till steg 1, medan mellanmatrisen har formen $(\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3})$ ${\begin{bmatrix}1&0&-1\\1&1&0\\1&0&2\end{bmatrix}}$

Utdata: bas reducerad med Lenstra-Lenstra-Lovas-metoden:

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

Applikation

Algoritmen används ofta inom MIMO- metoden (spatial signal coding) för att avkoda signaler som tas emot av flera antenner [10] och i kryptosystem med publik nyckel : kryptosystem baserade på ryggsäcksproblemet , RSA med specifika inställningar, NTRUEncrypt och så vidare . Algoritmen kan användas för att hitta heltalslösningar i olika problem inom talteorin, i synnerhet för att hitta rötterna till ett polynom i heltal [11] .

I processen med attacker mot kryptosystem med publik nyckel ( NTRU ) används algoritmen för att hitta den kortaste gittervektorn, eftersom algoritmen så småningom hittar en hel uppsättning kortaste vektorer [12] .

I RSA-krypteringsanalys med en liten CRT-exponent reduceras uppgiften, som i fallet med NTRU, till att hitta den kortaste gitterbasvektorn som finns i polynomtid (från basdimensionen) [13] .

I ryggsäcksproblem, i synnerhet för att attackera Merkle-Hellmans kryptosystem, söker LLL-algoritmen efter en reducerad gitterbas [14] .

Variationer och generaliseringar

Att använda flyttalsaritmetik istället för en exakt representation av rationella tal kan avsevärt påskynda LLL-algoritmen till priset av mycket små numeriska fel [15] .

Implementeringar av algoritmen

Programmatiskt implementeras algoritmen i följande mjukvara:

I fpLLL som en fristående implementering [16] ;
I GAP som funktion LLLReducedBasis [17] ;
I Macaulay2 som en funktion LLLi biblioteket LLLBases [18] ;
I Magma både funktioner LLLoch LLLGram [19] ;
I lönn som en funktion IntegerRelations[LLL] [20] ;
I Mathematica som funktion LatticeReduce [21] ;
I Number Theory Library (NTL) som en modul LLL [22] ;
I PARI/GP som en funktion qflll [23] ;
I Pymatgen som funktion analysis.get_lll_reduced_lattice [24] ;
I SageMath som en metod LLLimplementerad i fpLLL och NTL [25] .

Anteckningar

↑ 1 2 3 4 A. K. Lenstra, H. W. Lenstra Jr., L. Lovász. Faktorering av polynom med rationella koefficienter // Mathematische Annalen . - 1982. - S. 515-534 . — ISSN 4 . - doi : 10.1007/BF01457454 .
↑ 1 2 LLL-algoritmen, 2010 , 1 Historien om LLL-algoritmen.
↑ 1 2 3 4 5 6 7 Galbraith, Steven. 17. Lattice Reduction // Mathematics of Public Key Cryptography (engelska) . - 2012. Arkiverad 20 september 2015 på Wayback Machine
↑ 1 2 Xinyue, Deng. En introduktion till LLL Algorithm // Massachusetts Institute of Technology. - S. 9-10 . Arkiverad från originalet den 8 december 2019.
↑ Cherednik I. V. Icke-negativ gitterbas // 3rd ed. - Diskret. Mat., 2014. - T. 26 . - S. 127-135 . (ryska)
↑ 1 2 Regev, Oded. Gitter i datavetenskap: LLL Algorithm // New York University. Arkiverad från originalet den 20 mars 2021.
↑ 1 2 Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH En introduktion till matematisk kryptografi . — Springer, 2008. - S. 411. - ISBN 978-0-387-77993-5 .
↑ Nguyen, Phong Q., Stehlé, Damien. Reduktion av lågdimensionell gitterbas återbesökt // ACM Transactions on Algorithms. — S. 1–48 . - doi : 10.1145/1597036.1597050 .
↑ Bosma, Wieb. 4. LLL // Datoralgebra. - 2007. Arkiverad 8 maj 2019.
↑ Shahriar Shahabuddin, Janne Janhunen, Zaheer Khan, Markku Juntti, Amanullah Ghazi. En skräddarsydd multiprocessor för nätreducering för MIMO-detektering // 2015 IEEE International Symposium on Circuits and Systems (ISCAS). - 2015. - arXiv : 1501.04860 . - doi : 10.1109/ISCAS.2015.7169312 .
↑ D. Simon. Utvalda tillämpningar av LLL i talteori // LLL+25 Konferens. — Caen, Frankrike. Arkiverad 6 maj 2021.
↑ Abderrahmane, Nitaj. Krypteringsanalys av NTRU med två offentliga nycklar // International Association for Cryptologic Research. — Caen, Frankrike. Arkiverad från originalet den 21 december 2019.
↑ Bleichenbacher, Daniel och May, Alexander. Nya attacker mot RSA med små hemliga CRT-exponenter // International Association for Cryptologic Research. — Darmstadt, Tyskland. Arkiverad från originalet den 24 juni 2021.
↑ Liu, Jiayang, Bi, Jingguo och Xu, Songyan. En förbättrad attack mot de grundläggande Merkle–Hellman Knapsack-kryptosystemen // IEEE. — Peking 100084, Kina. Arkiverad från originalet den 17 juni 2021.
↑ The LLL Algorithm, 2010 , 4 Framsteg på LLL och gitterreduktion.
↑ FPLLL-utvecklingsteamet. FPLLL, ett gitterreduktionsbibliotek . — 2016. Arkiverad den 17 februari 2020.
↑ Integralmatriser och gitter . GAP . Hämtad 10 december 2019. Arkiverad från originalet 19 december 2019. (obestämd)
↑ LLLBaser -- gitterreduktion (Lenstra-Lenstra-Lovasz-baser) . Macaulay2 . Hämtad 10 december 2019. Arkiverad från originalet 10 december 2019. (obestämd)
↑ LLL-minskning . Magma . Hämtad 10 december 2019. Arkiverad från originalet 10 december 2019. (obestämd)
↑ IntegerRelations/LLL . lönn . Hämtad 10 december 2019. Arkiverad från originalet 18 september 2020. (obestämd)
↑ LatticeReduce . Wolfram språkdokumentation . Hämtad 10 december 2019. Arkiverad från originalet 10 december 2019. (obestämd)
↑ MODUL:LLL . NTL . Hämtad 10 december 2019. Arkiverad från originalet 17 augusti 2018. (obestämd)
↑ Vektorer, matriser, linjär algebra och mängder . PARI/GP . Hämtad 10 december 2019. Arkiverad från originalet 18 december 2019. (obestämd)
↑ pymatgen.core.lattice-modul . pymatgen . Hämtad 27 december 2019. Arkiverad från originalet 18 december 2019. (obestämd)
↑ Täta matriser över heltalsringen . salvia . Hämtad 18 december 2019. Arkiverad från originalet 6 maj 2021. (obestämd)

Litteratur

Huguette, Napias. En generalisering av LLL-algoritmen över euklidiska ringar eller order // J. The. Nombr. Bordeaux. - 1996. - doi : 10.5802/jtnb.176 .
Cohen, Henry. En kurs i beräkningsalgebraisk talteori (engelska) . — Springer, 2000. - Vol. 138. - (GTM). — ISBN 3-540-55640-0 .
Borwein, Peter. Beräkningsexkursioner i analys och talteori . - 2002. - ISBN 0-387-95444-9 .
Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH En introduktion till matematisk kryptografi . — Springer, 2008. - ISBN 978-0-387-77993-5 .
Luk, Franklin T.; Qiao, Sanzheng. En pivoterad LLL-algoritm // Lin. Alg. Appl.. - 2011. - T. 434 , nr 11 . - S. 2296-2307 . - doi : 10.1016/j.laa.2010.04.003 .
LLL Algorithm: Survey and Applications / Ed. av Phong Q. Nguyen och Brigitte Vallee. - Springer, 2010. - ISBN 978-3-642-02295-1 . - doi : 10.1007/978-3-642-02295-1 .
Murray R. Bremner. Lattice Basis Reduction: En introduktion till LLL-algoritmen och dess tillämpningar. - CRC Press, 2011. - ISBN 9781439807026 .

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm