Algoritme LLL

El algoritme de simplificació de bases de retículs de Lenstra–Lenstra–Lovász (LLL) és un algoritme de simplificació de retículs de complexitat polinomial inventat per Arjen Lenstra, Hendrik Lenstra i László Lovász en 1982. Donada una base $𝐁=\{{𝐛}_1,{𝐛}_2,\dots ,{𝐛}_d\}$ en coordenades sanceres n-dimensionals , d'un retícul L en Rⁿ en $d\le n$, l'algoritme LLL torna una base del retícul LLL-reduïda (menuda, casi ortogonal) en temps

$O(d^{5}n{\log }^{3}B)$

a on B és la llongitut més llarga dels $b_i$ baix la norma euclídea.

Les aplicacions originals eren donar algoritmes de complexitat polinomial para factorizar polinomis que coeficients racionals, per a trobar aproximacions racionals simultànees als número real, i per a resoldre el problema de la programació llineal sancera en dimensions fixades.

Simplificació de el LLL

La definició exacta de LLL-reduït és la següent: Donada una base

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

es definixen la seua base ortogonal obtinguda pel procés de ortogonalización de Gram-Schmidt

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

i els coeficients de Gram-Schmidt

${\mu }_{i,j}=\frac{⟨{𝐛}_i,{𝐛}_j^{*}⟩}{⟨{𝐛}_j^{*},{𝐛}_j^{*}⟩}$, per a cada $1\le j<i\le n$.

Llavors la base $B$ és LLL-reduïda si existix un paràmetro $\delta$ en (0.25,1] tal que es complixen les següents condicions:

1. (Tamany reduït) Para $1\le j<i\le n:\left|{\mu }_{i,j}\right|\le 0.5$. Per definició, esta propietat garantisa la reducció de la llongitut de la base.
2. (Condició de Lovász) Per a k = 2,3,..,n $:\delta \Vert {𝐛}_{k-1}^{*}{\Vert }^2\le \Vert {𝐛}_k^{*}{\Vert }^2+{\mu }_{k,k-1}^2\Vert {𝐛}_{k-1}^{*}{\Vert }^2$.

Aplegats a este punt, estimant el valor del paràmetro$\delta$, podem concloure cóm de be es reduïx la base. A majors valors de $\delta$ majors reduccions de la base. Inicialment, A. Lenstra, H. Lenstra and L. Lovász varen demostrar l'algoritme de simplificació LLL algoritme per a $\delta =\frac{3}{4}$. Note's que si ben l'algoritme de simplificació LLL està ben definit per a $\delta =1$, la complexitat de temps polinomial està garantisada solament per a $\delta \in (0.25,1)$ .

L'algoritme LLL calcula bases LLL-reduïdes. No es coneix un algoritme eficient que calcule una base que els seus vectores siguen tan menuts com siga possible per a retículs de dimensions majors que 4. No obstant, una base LLL-reduïda és casi tan chicoteta com siga possible, en li sentit de que hi ha unes cotes absolutes $c_i>1$ tal que el primer vector de la base no és més de $c_1$ voltes més llarc que el vector més curt del retícul, el segon vector de la base és igualment $c_2$ més llarc com a màxim que el segon vector més curt, i aixina successivament.

Implementacions en llenguages computacionals

LLL està implementat en

• Arageli com la funció lll_reduction_int.
• fpLLL com a implementació que s'eixecuta en local.
• GAP com la funció LLLReducedBasis.
• Macaulay2 com la funció LLL en el paquet LLLBases.
• Magma com les funcions LLL i LLLGram (prenent una matriu de Gram).
• Maple com la funció IntegerRelations[LLL].

• Mathematica com la funció LatticeReduce.
• Number Theory Library (NTL) com la funció LLL.
• PARI/GP com la funció qflll.
• Pymatgen com la funció analysis.get_lll_reduced_lattice.
• Sage com el método LLL portat a terme per fpLLL i NTL.

Vore també

• Método de Coppersmith

Bibliografia

• Cohen (2000). A course in computational algebraic number theory, Springer. ISBN 3-540-55640-0.
• Borwein, Peter (2002). Computational Excursions in Analysis and Number Theory. ISBN 0-387-95444-9.