Lenstra-Lenstra-Lovasův algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 19. března 2020; kontroly vyžadují 3 úpravy .

Algoritmus Lenstra-Lenstra-Lovas ( LLL-algorithm , LLL-algorithm ) je algoritmus redukce mřížkové báze vyvinutý Arjenem Lenstrou , Hendrikem Lenstrou a Laszlo Lovasem v roce 1982 [1] . V polynomiálním čase algoritmus transformuje bázi na mřížce (podskupině ) na nejkratší téměř ortogonální bázi na stejné mřížce. Od roku 2019 je algoritmus Lenstra-Lenstra-Lovas jedním z nejúčinnějších pro výpočet redukovaného základu v mřížích velkých $\mathbb {R} ^{n}$ rozměry . Je relevantní především v problémech, které se redukují na nalezení nejkratšího vektoru mřížky .

Historie

Algoritmus vyvinuli nizozemští matematici Arjen Lenstra a Hendrik Lenstra spolu s maďarským matematikem Laszlo Lovasem v roce 1982 [1] [2] .

Hlavním předpokladem pro vytvoření algoritmu LLL bylo, že Gramův–Schmidtův proces pracuje pouze s vektory, jejichž součástí jsou reálná čísla . Pro vektorový prostor umožňuje Gramův–Schmidtův proces transformovat libovolnou bázi na ortonormální („ideální“, k níž směřuje algoritmus LLL). Gram-Schmidtův proces však nezaručuje, že na výstupu bude každý z vektorů celočíselnou lineární kombinací původní báze. Výsledná sada vektorů tedy nemusí být základem původní mřížky. To vedlo k potřebě vytvořit speciální algoritmus pro práci s mřížemi [3] . $\mathbb {R} ^{n}$

Zpočátku byl algoritmus používán k faktorizaci polynomů s celočíselnými koeficienty , k výpočtu diofantických aproximací reálných čísel a k řešení problémů lineárního programování v prostorech s pevnými rozměry a později ke kryptoanalýze [4] [2] .

Snížení základu

Mříž v euklidovském prostoru je podskupina grupy generované lineárně nezávislými vektory z , nazývané základ mřížky. Libovolný vektor mřížky může být reprezentován celočíselnou lineární kombinací základních vektorů [5] . Základ mřížky je definován nejednoznačně: obrázek ukazuje dvě různé základny téže mřížky. $(\mathbb {R} ^{n},+)$ $d$ $\mathbb {R} ^{n}$

Redukce báze spočívá v uvedení mřížové báze do speciální formy, která splňuje určité vlastnosti. Redukovaná báze by měla být pokud možno nejkratší ze všech bází mřížky a blízká ortogonální (což je vyjádřeno tím, že konečné Gram-Schmidtovy koeficienty by neměly být větší než ) [3] . $1/2$

Nechť jako výsledek transformace báze pomocí Gram-Schmidtova procesu získáme bázi s Gram-Schmidtovými koeficienty definovanými následovně: $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\tečky ,\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 }}}

, pro všechny takové .

j,i

1\leqslant j<i\leqslant d

Potom se (uspořádaná) báze nazývá -LLL-redukovaná báze (kde parametr je v intervalu ), pokud splňuje následující vlastnosti [3] : $\mathbf {B}$ $\delta$ $\delta$ ${\textstyle (0,25,1]}$

Pro všechny takové . (podmínka snížení) $i,j$ $1\leqslant j<i\leqslant d\colon \left|\mu _{i,j}\right|\leqslant 0{,}5$
Pro chyty: . (Lovasův stav) $k=1,2,\tečky ,d$ $(\delta -\mu _{k,k-1}^{2})\|\mathbf {b} _{k-1}^{*}\|^{2}\leqslant \|\ mathbf {b} _{k}^{*}\|^{2}$

Zde je norma vektoru , je skalární součin vektorů. $\|\mathbf {b} \|$ $\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle$

Zpočátku Lenstra, Lenstra a Lovas ve svém článku demonstrovali fungování algoritmu pro parametr . Přestože algoritmus zůstává správný pro , jeho polynomiální časová operace je zaručena pouze pro v intervalu [1] . ${\textstyle \delta ={\frac {3}{4}}}$ $\delta=1$ $\delta$ $(0,25,1)$

Redukované základní vlastnosti

Dovolit být základem na mřížce zmenšené algoritmem LLL s parametrem . Z definice takového základu lze odvodit několik vlastností . Nechť je norma nejkratšího mřížkového vektoru, pak: $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\tečky ,\mathbf {b} _{d}\}$ $\delta$ ${\mathcal L}$ $\mathbf {B}$ $\lambda _{1}({\mathcal {L}})$

První základní vektor nemůže být výrazně delší než nejkratší nenulový vektor : ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\right)^{d-1}\cdot \lambda _{1}({\mathcal {L}})}$ . Zejména pro to se ukazuje [6] . $\delta =3/4$ $\|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/2}\cdot \lambda _{1}({\mathcal {L)))$
První bázový vektor je omezen mřížkovým determinantem : ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\right)^{(d-1)/ 2}\cdot \det({\mathcal {L}})^{1/d}}$ . Zejména pro to se ukazuje [3] . $\delta =3/4$ ${\displaystyle \|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/4}\cdot (\det {\mathcal {L)))^{1/d))$
Součin vektorových norem nemůže být mnohem větší než determinant mřížky: ${\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)))}$ . Zejména pro [3] . $\prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant 2^{d(d-1)/4}\cdot \det({\mathcal {L)))$ $\delta =3/4$

Báze transformovaná metodou LLL je téměř nejkratší možná v tom smyslu, že existují absolutní hranice tak, že první bázový vektor není více než krát delší než nejkratší mřížkový vektor, podobně druhý bázový vektor není delší než faktor druhého nejkratšího mřížkového vektoru a tak dále (což přímo vyplývá z vlastnosti 1) [6] . $c_{i}>1$ $c_{1}$ $c_{2}$

Algoritmus

Vstup [7] :

mřížková báze (skládá se z lineárně nezávislých vektorů),

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

parametr c , nejčastěji (volba parametru závisí na konkrétní úloze).

\delta

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

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

Pořadí akcí [4] :

Nejprve je vytvořena kopie původní báze, která je ortogonalizována tak, že v průběhu algoritmu je aktuální báze porovnávána s výslednou kopií na ortogonalitu ( ). $\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\tečky ,\mathbf {b} _{d}^{*}$
Pokud je jakýkoli Gram-Schmidtův koeficient (c ) v absolutní hodnotě větší než , pak je projekce jednoho z vektorů aktuální báze na vektor ortogonalizované báze s jiným číslem více než poloviční . To znamená, že je nutné od vektoru odečíst vektor vynásobený zaokrouhleným (zaokrouhlení je nutné, jelikož mřížkový vektor zůstává vektorem stejné mřížky pouze po vynásobení celým číslem, což vyplývá z jeho definice). Pak se zmenší , protože nyní bude projekce na méně než poloviční . Je tedy provedena kontrola splnění 1. podmínky z definice redukovaného základu CŽV. $\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}^{*}$
Přepočteno pro . ${\displaystyle \mu _{k,j))$ $j<k$
Pro je zaškrtnuta 2. podmínka zavedená autory algoritmu jako definice báze redukované LLL [1] . Pokud podmínka není splněna, pak se indexy zaškrtnutých vektorů prohodí. A znovu se kontroluje podmínka pro stejný vektor (již s novým indexem). ${\displaystyle \mathbf {b} _{k))$
Přepočteno pro a pro $\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$
Pokud zbyde nějaké, které překračuje v absolutní hodnotě (již s jiným ), pak se musíme vrátit k bodu 2. ${\displaystyle \mu _{k,j))$ $0{,}5$ $k$
Po zkontrolování všech podmínek a provedení změn se algoritmus ukončí.

V algoritmu - zaokrouhlování podle pravidel matematiky. Proces algoritmu, popsaný v pseudokódu [7] : $\lfloor \mu _{k,j}\rceil$

ortho

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

(proveďte Gram-Schmidtův proces bez normalizace); určit ,

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

vždy s uvedením nejaktuálnějších

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

dosud přiřazených

k=2

hodnot : pro j od do 0 : if , then : ; Aktualizovat hodnotypro; koncová podmínka ; konec cyklu ; if , then : else : swap and places; Aktualizovat hodnotypro; pro; ; koncová podmínka ; konec cyklu .

k\leqslant d

k-1

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

{\displaystyle \mathbf {b} _{k}=\mathbf {b} _{k}-\lpodlaží \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)

Výstupní údaje: redukovaný základ: . ${\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\tečky ,\mathbf {b} _{d))$

Výpočetní složitost

Vstup obsahuje základ -rozměrných vektorů s . $n$ $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\tečky ,\mathbf {b} _{d}\}$ $\ d\leqslant n$

Pokud se základní vektory skládají z celočíselných složek, algoritmus aproximuje nejkratší téměř ortogonální bázi v polynomiálním čase , kde je maximální délka v euklidovské normě , tj . Hlavní smyčka algoritmu LLL vyžaduje iterace a pracuje s čísly délky . Vzhledem k tomu, že vektory délky jsou zpracovávány při každé iteraci , v důsledku toho algoritmus vyžaduje aritmetické operace. Použití naivních algoritmů pro sčítání a násobení celých čísel vede k bitovým operacím [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)$

V případě, kdy má svaz základ s racionálními složkami, je třeba tato racionální čísla nejprve převést na celá čísla vynásobením vektorů báze jmenovateli jejich složek (množina jmenovatelů je omezena na nějaké celé číslo ). Ale pak budou operace prováděny již na celých číslech nepřesahujících . Výsledkem bude maximální počet bitových operací . Pro případ, kdy je mřížka uvedena v , zůstává složitost algoritmu stejná, ale zvyšuje se počet bitových operací. Protože v počítačové reprezentaci je jakékoli reálné číslo nahrazeno racionálním z důvodu omezenosti bitové reprezentace, výsledný odhad platí i pro reálné svazy [3] . $X$ ${\displaystyle X^{nd))$ $O(d^{8}n^{4}\log ^{3}X)$ $\mathbb {R} ^{n}$

Zároveň pro rozměry menší než 4 problém redukce báze efektivněji řeší Lagrangeův algoritmus [8] .

Příklad

Příklad uvedl Wib Bosma [9] .

Nechť je základ mřížky (jako podgrupa ) dán sloupci matice: $\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}}

V průběhu algoritmu se získá následující:

Gram-Schmidtův ortogonalizační proces
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)}$ a _ $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}})}$ , tedy a , pak a $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}}}$
Protože máme a , přejdeme k dalšímu kroku. $k=2$ $\mu _{2,1}<{\frac {1}{2}}$ $(\delta -\mu _{2,1}^{2})\|\mathbf {b} _{1}^{*}\|^{2}\leqslant \|\mathbf {b} _{2}^{*}\|^{2}$
Když máme: $k=3$
1. $\lfloor \mu _{3,2}\rceil =1$ znamená teď ${\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$ znamená teď ${\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}$ , takže mění místa. ${\displaystyle b_{3))$ $b_{2}$
Nyní se vrátíme ke kroku 1, zatímco mezilehlá matice má tvar $(\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3})$ ${\begin{bmatrix}1&0&-1\\1&1&0\\1&0&2\end{bmatrix}}$

Výstupní data: základ redukovaný metodou Lenstra-Lenstra-Lovas:

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

Aplikace

Algoritmus se často používá v rámci metody MIMO (kódování prostorového signálu) k dekódování signálů přijímaných více anténami [10] , a v kryptosystémech s veřejným klíčem : kryptosystémy založené na problému s batohem , RSA se specifickými nastaveními, NTRUEncrypt a tak dále . Algoritmus lze použít k nalezení celočíselných řešení v různých problémech teorie čísel, zejména k nalezení kořenů polynomu v celých číslech [11] .

V procesu útoků na kryptosystémy s veřejným klíčem ( NTRU ) se algoritmus používá k nalezení nejkratšího vektoru mřížky, protože algoritmus nakonec najde celou sadu nejkratších vektorů [12] .

V kryptoanalýze RSA s malým CRT-exponentem je úloha, stejně jako v případě NTRU, redukována na nalezení nejkratšího vektoru mřížky, který se nachází v polynomiálním čase (z dimenze báze) [13] .

V problémech s batohem, zejména při útoku na kryptosystém Merkle-Hellman, hledá algoritmus LLL redukovanou mřížkovou bázi [14] .

Variace a zobecnění

Použití aritmetiky s pohyblivou řádovou čárkou namísto přesné reprezentace racionálních čísel může výrazně urychlit algoritmus LLL za cenu velmi malých numerických chyb [15] .

Implementace algoritmu

Programově je algoritmus implementován v následujícím softwaru:

V fpLLL jako samostatná implementace [16] ;
V GAP jako funkce LLLReducedBasis [17] ;
V Macaulay2 jako funkce LLLv knihovně LLLBases [18] ;
V Magma obě funkce LLLa LLLGram [19] ;
V Maple jako funkce IntegerRelations[LLL] [20] ;
V Mathematica jako funkce LatticeReduce [21] ;
V knihovně teorie čísel (NTL) jako modul LLL [22] ;
V PARI/GP jako funkce qflll [23] ;
V Pymatgenu jako funkce analysis.get_lll_reduced_lattice [24] ;
V SageMath jako metoda LLLimplementovaná ve fpLLL a NTL [25] .

Poznámky

↑ 1 2 3 4 A. K. Lenstra, H. W. Lenstra ml., L. Lovász. Faktorování polynomů s racionálními koeficienty // 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. Redukce mřížky // Matematika kryptografie veřejného klíče (anglicky) . - 2012. Archivováno 20. září 2015 na Wayback Machine
↑ 1 2 Xinyue, Deng. Úvod do algoritmu LLL // Massachusetts Institute of Technology. - S. 9-10 . Archivováno z originálu 8. prosince 2019.
↑ Cherednik I. V. Nezáporná mřížková báze // 3. vyd. - Oddělený. Mat., 2014. - T. 26 . - S. 127-135 . (Ruština)
↑ 1 2 Regev, Oded. Lattices in Computer Science: LLL Algorithm // New York University. Archivováno z originálu 20. března 2021.
↑ 1 2 Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH Úvod do matematické kryptografie . — Springer, 2008. - S. 411. - ISBN 978-0-387-77993-5 .
↑ Nguyen, Phong Q., Stehlé, Damien. Redukce báze nízkorozměrné mřížky znovu prozkoumána // ACM Transactions on Algorithms. — S. 1–48 . - doi : 10.1145/1597036.1597050 .
↑ Bosma, Wieb. 4. LLL // Počítačová algebra. - 2007. Archivováno 8. května 2019.
↑ Shahriar Shahabuddin, Janne Janhunen, Zaheer Khan, Markku Juntti, Amanullah Ghazi. Přizpůsobený multiprocesor pro redukci mřížky pro detekci MIMO // 2015 IEEE International Symposium on Circuits and Systems (ISCAS). - 2015. - arXiv : 1501.04860 . - doi : 10.1109/ISCAS.2015.7169312 .
↑ D. Simon. Vybrané aplikace CŽV v teorii čísel // Konference LLL+25. — Caen, Francie. Archivováno 6. května 2021.
↑ Abderrahmane, Nitaj. Kryptoanalýza NTRU se dvěma veřejnými klíči // International Association for Cryptologic Research. — Caen, Francie. Archivováno z originálu 21. prosince 2019.
↑ Bleichenbacher, Daniel a May, Alexander. Nové útoky na RSA s malými tajnými exponenty CRT // Mezinárodní asociace pro kryptologický výzkum. — Darmstadt, Německo. Archivováno z originálu 24. června 2021.
↑ Liu, Jiayang, Bi, Jingguo a Xu, Songyan. Vylepšený útok na základní kryptosystémy Merkle–Hellman Knapsack // IEEE. — Peking 100084, Čína. Archivováno z originálu 17. června 2021.
↑ Algoritmus LLL, 2010 , 4 Pokrok v oblasti LLL a redukce mřížky.
↑ Vývojový tým FPLLL. FPLLL, knihovna pro redukci mřížky . — 2016. Archivováno 17. února 2020.
↑ Integrální matice a svazy . GAP . Staženo 10. prosince 2019. Archivováno z originálu 19. prosince 2019. (neurčitý)
↑ LLLBase -- redukce mřížky (Lenstra-Lenstra-Lovaszovy báze) . Macaulay2 . Staženo 10. prosince 2019. Archivováno z originálu 10. prosince 2019. (neurčitý)
↑ Snížení LLL . Magma . Staženo 10. prosince 2019. Archivováno z originálu 10. prosince 2019. (neurčitý)
↑ IntegerRelations/LLL . javor . Získáno 10. prosince 2019. Archivováno z originálu 18. září 2020. (neurčitý)
↑ LatticeReduce . Jazyková dokumentace Wolfram . Staženo 10. prosince 2019. Archivováno z originálu 10. prosince 2019. (neurčitý)
↑ MODUL:LLL . NTL . Získáno 10. prosince 2019. Archivováno z originálu 17. srpna 2018. (neurčitý)
↑ Vektory, matice, lineární algebra a množiny . PARI/GP . Staženo 10. prosince 2019. Archivováno z originálu 18. prosince 2019. (neurčitý)
↑ modul pymatgen.core.lattice . pymatgen . Staženo 27. prosince 2019. Archivováno z originálu 18. prosince 2019. (neurčitý)
↑ Husté matice přes celý kruh . šalvěj . Získáno 18. prosince 2019. Archivováno z originálu 6. května 2021. (neurčitý)

Literatura

Huguette, Napias. Zobecnění algoritmu LLL přes euklidovské kruhy nebo řády // J. The. Nombr. Bordeaux. - 1996. - doi : 10.5802/jtnb.176 .
Cohen, Henry. Kurz výpočetní algebraické teorie čísel (anglicky) . — Springer, 2000. - Sv. 138. - (GTM). — ISBN 3-540-55640-0 .
Borwein, Peter. Výpočetní exkurze v analýze a teorii čísel . - 2002. - ISBN 0-387-95444-9 .
Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH Úvod do matematické kryptografie . — Springer, 2008. - ISBN 978-0-387-77993-5 .
Luk, Franklin T.; Qiao, Sanzheng. Otočený algoritmus LLL // Lin. Alg. Přihláška - 2011. - T. 434 , č. 11 . - S. 2296-2307 . - doi : 10.1016/j.laa.2010.04.003 .
Algoritmus LLL: Průzkum a aplikace / Ed. od Phong Q. Nguyen a Brigitte Vallee. - Springer, 2010. - ISBN 978-3-642-02295-1 . - doi : 10.1007/978-3-642-02295-1 .
Murray R. Bremner. Redukce mřížkové báze: Úvod do algoritmu LLL a jeho aplikací. - CRC Press, 2011. - ISBN 9781439807026 .

Číselné teoretické algoritmy
Testy jednoduchosti	Mlynář Miller - Rabin Luca - Lemaire pepina Agravala - Kayala - Sasko Slavík - Strassen
Hledání prvočísel	Iterace přes dělitele Eratosthenovo síto Atkinovo síto Síto Sundarama
Faktorizace	Iterace přes dělitele Fermatova metoda p −1 Pollardova metoda Pollardův ρ-algoritmus Lehmannova metoda Metoda eliptické křivky (Lenstrův algoritmus) Dixonův algoritmus Čtvercové síto
Diskrétní logaritmus	Gelfond-Shanksův algoritmus Polig-Hellmanův algoritmus Pollardova ρ-metoda Pollardův algoritmus klokana Adlemanův algoritmus COS algoritmus
Hledání GCD	Euklidův algoritmus Pokročilý algoritmus Binární algoritmus
Modulová aritmetika	Montgomeryho algoritmus Čínská věta o zbytku
Násobení a dělení čísel	Algoritmus Karatsuba Toom-Cookův algoritmus Schönhage-Strassenův algoritmus Fuhrerův algoritmus Algoritmus Harvey-van der Hoeven Burnickel-Zieglerův algoritmus
Výpočet druhé odmocniny	Tonelli-Shanksův algoritmus Algoritmus Berlekamp-Rabin