Lenstra-Lenstra-Lovas algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 19. marts 2020; checks kræver 3 redigeringer .

Lenstra-Lenstra-Lovas- algoritmen ( LLL-algorithm , LLL-algorithm ) er en gitterbasisreduktionsalgoritme udviklet af Arjen Lenstra , Hendrik Lenstra og Laszlo Lovas i 1982 [1] . I polynomiel tid transformerer algoritmen en basis på et gitter (undergruppe ) til den korteste næsten ortogonale basis på samme gitter. Fra 2019 er Lenstra-Lenstra-Lovas-algoritmen en af de mest effektive til at beregne det reducerede grundlag i højdimensionelle gitter . Det er primært relevant i problemer, der reducerer til at finde den korteste gittervektor . $\mathbb {R} ^{n}$

Historie

Algoritmen blev udviklet af de hollandske matematikere Arjen Lenstra og Hendrik Lenstra sammen med den ungarske matematiker Laszlo Lovas i 1982 [1] [2] .

Hovedforudsætningen for oprettelsen af LLL-algoritmen var, at Gram-Schmidt-processen kun fungerer med vektorer, hvis komponenter er reelle tal . For et vektorrum gør Gram-Schmidt-processen det muligt at transformere et vilkårligt grundlag til et ortonormalt ("ideelt", som LLL-algoritmen har tendens til). Men Gram-Schmidt-processen garanterer ikke, at hver af vektorerne ved outputtet vil være en heltal lineær kombination af den oprindelige basis. Det resulterende sæt af vektorer er således muligvis ikke grundlaget for det oprindelige gitter. Dette førte til behovet for at skabe en speciel algoritme til at arbejde med gitter [3] . $\mathbb {R} ^{n}$

Oprindeligt blev algoritmen brugt til at faktorisere polynomier med heltalskoefficienter , beregne diofantiske tilnærmelser af reelle tal og til at løse lineære programmeringsproblemer i fastdimensionelle rum og senere til kryptoanalyse [4] [2] .

Basisreduktion

Et gitter i det euklidiske rum er en undergruppe af gruppen genereret af lineært uafhængige vektorer fra , kaldet basis for gitteret. Enhver gittervektor kan repræsenteres af en heltal lineær kombination af basisvektorer [5] . Grundlaget for et gitter er defineret tvetydigt: figuren viser to forskellige baser af det samme gitter. $(\mathbb {R} ^{n},+)$ $d$ $\mathbb {R} ^{n}$

Basisreduktion består i at bringe gittergrundlaget til en særlig form, der tilfredsstiller bestemte egenskaber. Den reducerede basis bør om muligt være den korteste blandt alle baserne i gitteret og tæt på ortogonal (hvilket kommer til udtryk i, at de endelige Gram-Schmidt-koefficienter ikke bør være mere end ) [3] . $1/2$

Lad, som et resultat af transformationen af grundlaget ved hjælp af Gram-Schmidt-processen , få grundlaget med Gram-Schmidt-koefficienterne defineret som følger: $\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 }}}

, for alt sådan .

j,i

1\leqslant j<i\leqslant d

Så kaldes en (ordnet) basis en -LLL-reduceret basis (hvor parameteren er i intervallet ), hvis den opfylder følgende egenskaber [3] : $\mathbf {B}$ $\delta$ $\delta$ ${\textstyle (0.25,1]}$

For alt sådan . (reduktionsbetingelse) $i,j$ $1\leqslant j<i\leqslant d\colon \left|\mu _{i,j}\right|\leqslant 0{,}5$
Til rummer :. (Lovas tilstand) $k=1,2,\dots ,d$ $(\delta -\mu _{k,k-1}^{2})\|\mathbf {b} _{k-1}^{*}\|^{2}\leqslant \|\ mathbf {b} _{k}^{*}\|^{2}$

Her er normen for vektoren , er det skalære produkt af vektorer. $\|\mathbf {b} \|$ $\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle$

Indledningsvis demonstrerede Lenstra, Lenstra og Lovas driften af algoritmen for parameteren i deres papir . Selvom algoritmen forbliver korrekt for , er dens polynomielle tidsdrift kun garanteret i intervallet [1] . ${\textstyle \delta ={\frac {3}{4}}}$ $\delta=1$ $\delta$ $(0.25,1)$

Reducerede basisegenskaber

Lade være et grundlag på gitteret reduceret af LLL-algoritmen med parameteren . Flere egenskaber kan udledes af definitionen af et sådant grundlag . Lad være normen for den korteste gittervektor, så : $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $\delta$ ${\mathcal L}$ $\mathbf {B}$ $\lambda _{1}({\mathcal {L}})$

Den første basisvektor kan ikke være væsentlig længere end den korteste ikke-nulvektor : ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\right)^{d-1}\cdot \lambda _{1}({\mathcal {L}})}$ . Især, for det viser sig [6] . $\delta =3/4$ $\|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/2}\cdot \lambda _{1}({\mathcal {L)))$
Den første basisvektor er begrænset af gitterdeterminanten : ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\right)^{(d-1)/ 2}\cdot \det({\mathcal {L}})^{1/d}}$ . Især, for det viser sig [3] . $\delta =3/4$ ${\displaystyle \|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/4}\cdot (\det {\mathcal {L)))^{1/d))$
Produktet af vektornormer kan ikke være meget større end gitterets 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)))}$ . Især for [3] . $\prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant 2^{d(d-1)/4}\cdot \det({\mathcal {L)))$ $\delta =3/4$

Grundlaget transformeret ved LLL-metoden er næsten den kortest mulige, i den forstand, at der er absolutte grænser , således at den første basisvektor ikke er mere end gange så lang som den korteste gittervektor, ligesom den anden basisvektor ikke er mere end en faktor af den anden den korteste gittervektor, og så videre (som følger direkte af egenskab 1) [6] . $c_{i}>1$ $c_{1}$ $c_{2}$

Algoritme

Input [7] :

gitterbasis (består af lineært uafhængige vektorer),

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

parameter c , oftest (valget af parameter afhænger af den specifikke opgave).

\delta

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

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

Handlingssekvens [4] :

Først oprettes en kopi af det originale grundlag, som ortogonaliseres, således at det aktuelle grundlag i løbet af algoritmen sammenlignes med den resulterende kopi for ortogonalitet ( ). $\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{d}^{*}$
Hvis nogen Gram-Schmidt-koefficient (c ) er større i absolut værdi end , så er projektionen af en af vektorerne af det aktuelle grundlag på vektoren af en ortogonaliseret basis med et andet tal mere end halvdelen . Det betyder, at det er nødvendigt at trække vektoren ganget med den afrundede fra vektoren (afrunding er nødvendig, da gittervektoren kun forbliver vektoren af det samme gitter, når den multipliceres med et heltal, hvilket følger af dens definition). Så bliver det mindre , da fremskrivningen på nu bliver mindre end det halve . Der foretages således kontrol for overholdelse af 1. betingelse fra definitionen af et LLL-reduceret grundlag. $\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}^{*}$
Genberegnet til . ${\displaystyle \mu _{k,j))$ $j<k$
For er den 2. betingelse kontrolleret, indført af forfatterne af algoritmen som definitionen af et LLL-reduceret grundlag [1] . Hvis betingelsen ikke er opfyldt, byttes indeksene for de kontrollerede vektorer. Og betingelsen kontrolleres igen for den samme vektor (allerede med et nyt indeks). ${\displaystyle \mathbf {b} _{k))$
Genberegnet for og for $\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$
Hvis der er nogen tilbage, der overstiger i absolut værdi (allerede med en anden ), så skal vi tilbage til punkt 2. ${\displaystyle \mu _{k,j))$ $0{,}5$ $k$
Når alle betingelser er kontrolleret og ændringer er foretaget, afsluttes algoritmen.

I algoritmen - afrunding efter matematikkens regler. Processen med algoritmen, beskrevet i pseudokode [7] : $\lfloor \mu _{k,j}\rceil$

ortho

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

(udfør Gram-Schmidt-processen uden normalisering); bestemme ,

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

altid med de mest aktuelle værdier

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

tildele

k=2

indtil

k\leqslant d

videre : for j fra til 0 : hvis , så :; Opdater værdierfor; endetilstand ; _ slutningen af cyklussen ; hvis , så : andet : bytte og steder; Opdater værdierfor; for; ; endetilstand ; _ slutningen af cyklussen .

k-1

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

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

|\mu _{k,j}|

j<k

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

Outputdata: reduceret grundlag: . ${\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d))$

Beregningsmæssig kompleksitet

Inputtet indeholder en basis af dimensionelle vektorer med . $n$ $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $\ d\leqslant n$

Hvis basisvektorerne består af heltalskomponenter, tilnærmer algoritmen den korteste næsten ortogonale basis i polynomiel tid , hvor er den maksimale længde i den euklidiske norm , dvs. Hovedsløjfen i LLL-algoritmen kræver iterationer og arbejder med længdenumre . Da længdevektorer behandles ved hver iteration , kræver algoritmen aritmetiske operationer. Brugen af naive algoritmer til addition og multiplikation af heltal resulterer i bitvise 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 tilfælde, hvor gitteret har en basis med rationelle komponenter, skal disse rationelle tal først konverteres til heltal ved at gange basisvektorerne med nævnerne af deres komponenter (sættet af nævnere er begrænset til et eller andet heltal ). Men så vil operationer allerede blive udført på heltal, der ikke overstiger . Som et resultat vil der være et maksimum af bit-operationer . I det tilfælde, hvor gitteret er givet i , forbliver kompleksiteten af algoritmen den samme, men antallet af bitoperationer stiger. Da et hvilket som helst reelt tal i computerrepræsentationen erstattes af et rationelt tal på grund af bitrepræsentationens begrænsethed, er det resulterende estimat også sandt for reelle gitter [3] . $x$ ${\displaystyle X^{nd))$ $O(d^{8}n^{4}\log ^{3}X)$ $\mathbb {R} ^{n}$

På samme tid, for dimensioner mindre end 4, løses problemet med basisreduktion mere effektivt af Lagrange-algoritmen [8] .

Eksempel

Et eksempel givet af Wib Bosma [9] .

Lad grundlaget for gitteret (som en undergruppe ) være givet af søjlerne i matrixen: $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\i \displaystyle \mathbb {Z} ^{3}$ $(\mathbb {R} ^{n},+)$

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

I løbet af algoritmen opnås følgende:

Gram-Schmidt ortogonaliseringsproces
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)}$ , og $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}})}$ , derfor og , så og $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}}}$
For vi har og , så vi går til næste trin. $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}}}$ ${\textstyle \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}}}$ ${\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}$ , så de skifter plads. ${\displaystyle b_{3))$ ${\displaystyle b_{2))$
Nu vender vi tilbage til trin 1, mens den mellemliggende matrix har formen $(\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3})$ ${\begin{bmatrix}1&0&-1\\1&1&0\\1&0&2\end{bmatrix}}$

Outputdata: basis reduceret med Lenstra-Lenstra-Lovas-metoden:

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

Ansøgning

Algoritmen bruges ofte inden for MIMO -metoden (spatial signal coding) til at afkode signaler modtaget af flere antenner [10] , og i offentlige nøglekryptosystemer : kryptosystemer baseret på rygsækproblemet , RSA med specifikke indstillinger, NTRUEncrypt og så videre . Algoritmen kan bruges til at finde heltalsløsninger i forskellige talteoriproblemer, især til at finde rødderne til et polynomium i heltal [11] .

I processen med angreb på offentlige nøglekryptosystemer ( NTRU ) bruges algoritmen til at finde den korteste gittervektor, da algoritmen til sidst finder et helt sæt korteste vektorer [12] .

I RSA-kryptanalyse med en lille CRT-eksponent er opgaven, som i tilfældet med NTRU, reduceret til at finde den korteste gitterbasisvektor, der findes i polynomiel tid (fra basisdimensionen) [13] .

I rygsækproblemer, især for at angribe Merkle-Hellman-kryptosystemet, søger LLL-algoritmen efter en reduceret gitterbasis [14] .

Variationer og generaliseringer

Brug af flydende komma -aritmetik i stedet for en nøjagtig repræsentation af rationelle tal kan fremskynde LLL-algoritmen betydeligt på bekostning af meget små numeriske fejl [15] .

Implementeringer af algoritmen

Programmatisk er algoritmen implementeret i følgende software:

I fpLLL som en selvstændig implementering [16] ;
I GAP som funktion LLLReducedBasis [17] ;
I Macaulay2 som en funktion LLLi biblioteket LLLBases [18] ;
I Magma både funktioner LLLog LLLGram [19] ;
I Maple som funktion IntegerRelations[LLL] [20] ;
I Mathematica som funktion LatticeReduce [21] ;
I Talteoribiblioteket (NTL) som et modul LLL [22] ;
I PARI/GP som en funktion qflll [23] ;
I Pymatgen som funktion analysis.get_lll_reduced_lattice [24] ;
I SageMath som metode LLLimplementeret i fpLLL og NTL [25] .

Noter

↑ 1 2 3 4 A. K. Lenstra, H. W. Lenstra Jr., L. Lovász. Faktorering af polynomier med rationelle koefficienter // Mathematische Annalen . - 1982. - S. 515-534 . — ISSN 4 . - doi : 10.1007/BF01457454 .
↑ 1 2 The LLL Algorithm, 2010 , 1 The History of the LLL-Algorithm.
↑ 1 2 3 4 5 6 7 Galbraith, Steven. 17. Lattice Reduction // Mathematics of Public Key Cryptography (engelsk) . - 2012. Arkiveret 20. september 2015 på Wayback Machine
↑ 1 2 Xinyue, Deng. En introduktion til LLL-algoritme // Massachusetts Institute of Technology. - S. 9-10 . Arkiveret fra originalen den 8. december 2019.
↑ Cherednik I. V. Ikke-negativ gitterbasis // 3. udg. — Diskret. Mat., 2014. - T. 26 . - S. 127-135 . (Russisk)
↑ 1 2 Regev, Oded. Gitter i datalogi: LLL Algorithm // New York University. Arkiveret fra originalen den 20. marts 2021.
↑ 1 2 Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH En introduktion til matematisk kryptografi . — Springer, 2008. - S. 411. - ISBN 978-0-387-77993-5 .
↑ Nguyen, Phong Q., Stehlé, Damien. Lavdimensionel gitterbasisreduktion genbesøgt // ACM Transactions on Algoritms. — S. 1–48 . - doi : 10.1145/1597036.1597050 .
↑ Bosma, Wieb. 4. LLL // Computeralgebra. - 2007. Arkiveret 8. maj 2019.
↑ Shahriar Shahabuddin, Janne Janhunen, Zaheer Khan, Markku Juntti, Amanullah Ghazi. En tilpasset gitterreduktion multiprocessor til MIMO-detektion // 2015 IEEE International Symposium on Circuits and Systems (ISCAS). - 2015. - arXiv : 1501.04860 . - doi : 10.1109/ISCAS.2015.7169312 .
↑ D. Simon. Udvalgte anvendelser af LLL i talteori // LLL+25 Konference. - Caen, Frankrig. Arkiveret 6. maj 2021.
↑ Abderrahmane, Nitaj. Krypteringsanalyse af NTRU med to offentlige nøgler // International Association for Cryptologic Research. - Caen, Frankrig. Arkiveret fra originalen den 21. december 2019.
↑ Bleichenbacher, Daniel og May, Alexander. Nye angreb på RSA med små hemmelige CRT-eksponenter // International Association for Cryptologic Research. — Darmstadt, Tyskland. Arkiveret fra originalen den 24. juni 2021.
↑ Liu, Jiayang, Bi, Jingguo og Xu, Songyan. Et forbedret angreb på de grundlæggende Merkle-Hellman Knapsack Cryptosystems // IEEE. — Beijing 100084, Kina. Arkiveret fra originalen den 17. juni 2021.
↑ The LLL Algorithm, 2010 , 4 Fremskridt med hensyn til LLL og Lattice Reduction.
↑ FPLLL-udviklingsteamet. FPLLL, et gitterreduktionsbibliotek . — 2016. Arkiveret den 17. februar 2020.
↑ Integralmatricer og gitter . GAP . Hentet 10. december 2019. Arkiveret fra originalen 19. december 2019. (ubestemt)
↑ LLLBaser -- gitterreduktion (Lenstra-Lenstra-Lovasz-baser) . Macaulay 2 . Hentet 10. december 2019. Arkiveret fra originalen 10. december 2019. (ubestemt)
↑ LLL-reduktion . Magma . Hentet 10. december 2019. Arkiveret fra originalen 10. december 2019. (ubestemt)
↑ IntegerRelations/LLL . ahorn . Hentet 10. december 2019. Arkiveret fra originalen 18. september 2020. (ubestemt)
↑ LatticeReduce . Wolfram sprogdokumentation . Hentet 10. december 2019. Arkiveret fra originalen 10. december 2019. (ubestemt)
↑ MODUL:LLL . NTL . Hentet 10. december 2019. Arkiveret fra originalen 17. august 2018. (ubestemt)
↑ Vektorer, matricer, lineær algebra og mængder . PARI/GP . Hentet 10. december 2019. Arkiveret fra originalen 18. december 2019. (ubestemt)
↑ pymatgen.core.lattice modul . pymatgen . Hentet 27. december 2019. Arkiveret fra originalen 18. december 2019. (ubestemt)
↑ Tætte matricer over heltalsringen . salvie . Hentet 18. december 2019. Arkiveret fra originalen 6. maj 2021. (ubestemt)

Litteratur

Huguette, Napias. En generalisering af LLL-algoritmen over euklidiske ringe eller ordrer // J. The. Nombr. Bordeaux. - 1996. - doi : 10.5802/jtnb.176 .
Cohen, Henry. Et kursus i beregningsmæssig algebraisk talteori (engelsk) . — Springer, 2000. - Vol. 138. - (GTM). — ISBN 3-540-55640-0 .
Borwein, Peter. Beregningsudflugter i analyse og talteori . - 2002. - ISBN 0-387-95444-9 .
Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH En introduktion til matematisk kryptografi . — Springer, 2008. - ISBN 978-0-387-77993-5 .
Luk, Franklin T.; Qiao, Sanzheng. En pivoteret LLL-algoritme // Lin. Alg. Ansøgning.. - 2011. - T. 434 , nr. 11 . - S. 2296-2307 . - doi : 10.1016/j.laa.2010.04.003 .
LLL-algoritmen: undersøgelse og applikationer / Ed. af Phong Q. Nguyen og Brigitte Vallee. - Springer, 2010. - ISBN 978-3-642-02295-1 . - doi : 10.1007/978-3-642-02295-1 .
Murray R. Bremner. Lattice Basisreduktion: En introduktion til LLL-algoritmen og dens applikationer. - CRC Press, 2011. - ISBN 9781439807026 .

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme