Algoritmus LLL

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

Pro zadanou bázi mříže

B = { b 0 , b 1 , … , b n } , {\displaystyle \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í:

B ∗ = { b 0 ∗ , b 1 ∗ , … , b n ∗ } , {\displaystyle \mathbf {B} ^{*}=\{\mathbf {b} _{0}^{*},\mathbf {b} _{1}^{*},\dots ,\mathbf {b} _{n}^{*}\},}

a koeficienty

μ i , j = ⟨ b i , b j ∗ ⟩ ⟨ b j ∗ , b j ∗ ⟩ {\displaystyle \mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}} , pro všechna 1 ≤ j < i ≤ n {\displaystyle 1\leq j<i\leq n} .

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

  1. Pro 1 ≤ j < i ≤ n : | μ i , j | ≤ 1 4 {\displaystyle 1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq {\frac {1}{4}}}
  2. Pro k = 1,2,..,n : δ ‖ b k − 1 ∗ ‖ 2 ≤ ‖ b k ∗ ‖ 2 + μ k , k − 1 2 ‖ b k − 1 ∗ ‖ 2 {\displaystyle \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.

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

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.