Algoritmus LLL

Algoritmus LLL (také L^3[1]), rozepsaně Lenstrův-Lenstrův-Lovászův algoritmus pro redukci báze mříže je polynomický algoritmus publikovaný v roce 1982 Arjenem Lenstrou, Hendrikem Lenstrou a László Lovászem a sloužící k nalezení redukované báze dané bodové mříže. Pro bodové mříže v prostoru o pěti a více rozměrech není znám žádný efektivní algoritmus pro nalezení nejkratší báze dané mříže, ale v řadě aplikací je postačující najít jeho aproximaci, kterou je možné efektivně najít právě algoritmem LLL.

Původní aplikací metody bylo hledání rozkladu polynomů s racionálními koeficienty, ale později našla daleko rozmanitější uplatnění při řešení rozmanitých úloh na bodových mřížích. Patřičné problémy se objevují například v kryptoanalýze některých asymetrických šifer (například RSA a NTRUEncrypt) nebo v rámci lineárního programování.

Pro zadanou bázi mříže

${\displaystyle \mathbf {B} =\{\mathbf {b} _{0},\mathbf {b} _{1},\dots ,\mathbf {b} _{n}\},}$

je uvažována ortogonální báze získaná Gramovou-Schmidtovou ortogonalizací:

${\displaystyle \mathbf {B} ^{*}=\{\mathbf {b} _{0}^{*},\mathbf {b} _{1}^{*},\dots ,\mathbf {b} _{n}^{*}\},}$

a koeficienty

${\displaystyle \mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}}$, pro všechna ${\displaystyle 1\leq j<i\leq n}$.

Báze ${\displaystyle B}$ je považována za LLL-redukovanou s parametrem ${\displaystyle \delta \in (1/4,1)}$, pokud jsou splněny dvě podmínky:

1. Pro ${\displaystyle 1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq {\frac {1}{4}}}$
2. Pro k = 1,2,..,n ${\displaystyle \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}}$

Algoritmus LLL je součástí řady výpočetních prostředí a programových knihoven, například:

• GAP nabízí funkci LLLReducedBasis
• Maple nabízí funkci IntegerRelations[LLL]
• Mathematica nabízí funkci LatticeReduce
• PARI/GP nabízí funkci qflll
• SageMath nabízí funkci LLL

V tomto článku byl použit překlad textu z článku Lenstra–Lenstra–Lovász lattice basis reduction algorithm na anglické Wikipedii.

• LENSTRA, Arjen; LENSTRA, Hendrik; LOVÁSZ, László. Factoring polynomials with rational coefficients. Mathematische Annalen. Prosinec 1982, roč. 261, čís. 4. Dostupné online. 
• STANOVSKÝ, David; BARTO, Libor. Počítačová algebra. Praha: Matfyzpress, 2011. ISBN 978-80-7378-167-5. S. 159-178.