Algoritmus 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
je uvažována ortogonální báze získaná Gramovou-Schmidtovou ortogonalizací:
a koeficienty , pro všechna .
Báze je považována za LLL-redukovanou s parametrem , pokud jsou splněny dvě podmínky: Pro Pro k = 1,2,..,n
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
Literatura
Kategorie:Bodová mříž Kategorie:Výpočtová teorie čísel