Algoritmus LLL

Algoritmus LLL (také L³), 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í.

LLL-redukovaná báze

Pro zadanou bázi mříže

$\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í:

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

a koeficienty

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

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

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

Implementace

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

Odkazy

Reference

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

Literatura

• 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. 

Portály: Matematika