Algoritmus LLL

Z Wikipedie, otevřené encyklopedie

Algoritmus LLL (také L3[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í.

LLL-redukovaná báze[editovat | editovat zdroj]

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:

  1. Pro
  2. Pro k = 1,2,..,n

Implementace[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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

  1. KNUTH, Donald E. Umění programování 2. díl – Seminumerické algoritmy. Brno: Computer Press, 2010. ISBN 978-80-251-2898-5. 

Literatura[editovat | editovat zdroj]