Cesko.wiki Algoritmus LLL
Author
Albert FloresAlgoritmus LLL (také L3), 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 \le j .
Báze B je považována za LLL-redukovanou s parametrem \delta \in (1/4,1), pokud jsou splněny dvě podmínky: # Pro 1 \leq j # 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