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

$𝐁=\{{𝐛}_0,{𝐛}_1,\dots ,{𝐛}_n\},$

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

${𝐁}^{*}=\{{𝐛}_0^{*},{𝐛}_1^{*},\dots ,{𝐛}_n^{*}\},$

a koeficienty

${\mu }_{i,j}=\frac{⟨{𝐛}_i,{𝐛}_j^{*}⟩}{⟨{𝐛}_j^{*},{𝐛}_j^{*}⟩}$, pro všechna $1\le j<i\le 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\le j<i\le n:\left|{\mu }_{i,j}\right|\le \frac{1}{4}$
2. Pro k = 1,2,..,n $:\delta \Vert {𝐛}_{k-1}^{*}{\Vert }^2\le \Vert {𝐛}_k^{*}{\Vert }^2+{\mu }_{k,k-1}^2\Vert {𝐛}_{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

Literatura

• Šablona:Citace periodika
• Šablona:Citace monografie