Lenstra–Lenstra–Lovász gitterbasreduktionsalgoritm

Lenstra –Lenstra–Lovász (LLL) gitterbasreduktionsalgoritm är en polynomisk tidsgitterreduktionsalgoritm som uppfanns av Arjen Lenstra $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ Hendrik Lenstra och László Lovász 1982. Givet basen , med n -dimensionella heltalskoordinater, för ett gitter L (en diskret undergrupp av Rn ) med $d\leq n$ , beräknar LLL-algoritmen en LLL-reducerad ⁽ kort, nästan ortogonal ) gitterbas i tid

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

där $B$ är den största längden av $\mathbf {b} _{i}$ under den euklidiska normen , det vill säga $B=\max \left(\|\mathbf {b} _{1}\|_{2},\|\mathbf {b} _{2}\| _{2},\dots ,\|\mathbf {b} _{d}\|_{2}\right)$ .

De ursprungliga applikationerna var att ge polynom-tidsalgoritmer för att faktorisera polynom med rationella koefficienter, för att hitta samtidiga rationella approximationer till reella tal och för att lösa heltalslinjärprogrammeringsproblemet i fasta dimensioner.

LLL-reduktion

Den exakta definitionen av LLL-reducerad är som följer: Givet en grund

$$\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\ mathbf {b} _{n}\},$$

definiera sin Gram-Schmidt-process ortogonala grund

$$\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},$$

och Gram-Schmidt-koefficienterna

$$\mu _{i,j}={\frac {\langle \mathbf {b} _{i} ,\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle } },$$

för vilken som helst $1\leq j<i\leq n$ .

Då är basen $B$ LLL-reducerad om det finns en parameter $\delta$ i (0.25, 1] ​​så att följande gäller:

1. (storleksreducerad) För $1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0,5$ . Per definition garanterar denna egenskap längdminskningen av det beställda underlaget.
2. $Lovász -villkor) För k = 2,3$ ..,n .

Här, genom att uppskatta värdet på parametern $\delta$ , kan vi dra slutsatsen hur väl basen reduceras. Större värden på $\delta$ leder till starkare reduktioner av basen. Inledningsvis demonstrerade A. Lenstra, H. Lenstra och L. Lovász LLL-reduktionsalgoritmen för $\delta ={\frac {3}{4}}$ . Observera att även om LLL-reduktion är väldefinierad för $\delta =1$ , garanteras polynom-tidskomplexiteten endast för $\delta$ i $(0.25,1)$ .

LLL-algoritmen beräknar LLL-reducerade baser. Det finns ingen känd effektiv algoritm för att beräkna en bas där basvektorerna är så korta som möjligt för gitter med dimensioner större än 4. En LLL-reducerad bas är dock nästan så kort som möjligt, i den meningen att det finns absoluta gränser $c_{i}>1$ så att den första basvektorn inte är mer än $c_{1}$ gånger så lång som en kortaste vektor i gittret, den andra basvektorn är likaså inom $c_{2}$ av det andra på varandra följande minimum, och så vidare.

Ansökningar

En tidig framgångsrik tillämpning av LLL-algoritmen var dess användning av Andrew Odlyzko och Herman te Riele för att motbevisa Mertens gissningar .

LLL-algoritmen har hittat många andra tillämpningar i MIMO- detekteringsalgoritmer och kryptoanalys av krypteringsscheman med offentliga nyckel : ryggsäckskryptosystem , RSA med särskilda inställningar, NTRUEncrypt , och så vidare. Algoritmen kan användas för att hitta heltalslösningar på många problem.

I synnerhet bildar LLL-algoritmen en kärna av en av heltalsrelationsalgoritmerna . Till exempel, om man tror att r =1,618034 är en (något avrundad) rot till en okänd kvadratisk ekvation med heltalskoefficienter, kan man tillämpa LLL-reduktion på gittret i $\mathbf {Z} ^{4}$ spänns av $[1,0,0,10000r^{2}],[0,1,0,10000r],$ och $[0,0,1,10000 ]$ . Den första vektorn i den reducerade basen kommer att vara en heltalslinjär kombination av dessa tre, alltså nödvändigtvis av formen $[a,b,c,10000(ar^{2}+br+c)]$ ; men en sådan vektor är "kort" bara om a , b , c är små och $ar^{2}+br+c$ är ännu mindre. Således är de tre första ingångarna i denna korta vektor sannolikt koefficienterna för det andragradspolynom som har r som en rot. I det här exemplet finner LLL-algoritmen att den kortaste vektorn är [1, -1, -1, 0,00025] och faktiskt $x^{2}-x-1$ har en rot som är lika med det gyllene snittet , 1,6180339887....

Egenskaper för LLL-reducerad grund

Låt $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\ mathbf {b} _{n}\}$ vara en $\delta$ -LLL-reducerad bas av ett gitter ${\mathcal {L}}$ . Från definitionen av LLL-reducerad basis kan vi härleda flera andra användbara egenskaper om $\mathbf {B}$ .

1. Den första vektorn i basen kan inte vara mycket större än den kortaste vektorn som inte är noll : $\Vert \mathbf { b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{n-1}\cdot \lambda _{1}({\mathcal {L}})$ . Speciellt för ${\displaystyle \delta =3/$ , detta ger $\Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/2 }\cdot \lambda _{1}({\mathcal {L}})$ .
2. Den första vektorn i basen är också begränsad av gittrets determinant: ${\ displaystyle \Vert \mathbf {b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{(n-1)/2}\cdot (\det({ \mathcal {L}}))^{1/n}}$ . I synnerhet för $\delta =3/4$ ger $\Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}$ .
3. Produkten av normerna för vektorerna i basen kan inte vara mycket större än gittrets determinant: låt ${\displaystyle \delta =3/4} ,$ då ${\textstyle \prod _{i=1}^{n}\Vert \mathbf {b} _{i}\Vert \leq 2^{n(n -1)/4}\cdot \det({\mathcal {L}})}$ .

LLL algoritm pseudokod

Följande beskrivning är baserad på ( Hoffstein, Pipher & Silverman 2008 , Theorem 6.68), med korrigeringarna från erratan.

0
    00
     INPUT  en gitterbas  b  ,  b  1  , ...,  b  n  i  Z  m  en parameter  δ  med 1/4 <  δ  < 1, oftast  δ  = 3/4  PROCEDUR  B  *  <- GramSchmidt({  b  , ... ,  bn  }) = {  b  *  , ...  ,  bn  *  }  ;  och normalisera inte  μ  i  ,  j  
      
            0 
             <- InnerProduct(  b  i  ,  b  j  *  )/InnerProduct(  b  j  *  ,  b  j  *  );  använda  de mest aktuella värdena för  bi  och  b  j  *  k  <- 1;  medan  k  <=  n  gör  för  j  från  k  −1  att  göra  om  |  μk  _  ,  j  |  > 1/2 
                   
                   
                00 sedan  b  k  <-  b  k  − ⌊  μ  k  ,  j  ⌉  b  j  ;  Uppdatera  B  *  och relaterade  μ  i  ,  j  efter behov.  (Den naiva metoden är att beräkna  B  *  närhelst  b  i  ändras:  B  *  <- GramSchmidt({  b  , ...,  b  n  }) = {  b  *  , ..., 
        
        
             b  n  *  })  end if  end för  if  InnerProduct(  b  k  *  ,  b  k  *  ) > (  δ − μ  2  k  ,  k  −1  ) InnerProduct(  b  k  −1  *  ,  b  k  −1  *  )  sedan  k  <-  k  + 1;  annars  Byt  b  k  och  b    
            
    
     00 k  -1  ;  Uppdatera  B  *  och relaterade  μ  i  ,  j  efter behov.  k  <- max(  k  -1, 1);  end if  end while  return  B  den LLL reducerade basen av {b  , ..., b  n  }  OUTPUT  den reducerade basen  b  ,  b  1  , ...,  b  n  i  Z  m 

Exempel

Exempel från Z ³

Låt ett gitterbas $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in \ mathbf {Z} ^{3}$ , ges av kolumnerna för

$${\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}$$

då är det reducerade underlaget

$${\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}},$$

som är storleksreducerad, uppfyller Lovász-villkoret och är därför LLL-reducerad, som beskrivits ovan. Se W. Bosma. för detaljer om reduktionsprocessen.

Exempel från Z[ i ] ⁴

På samma sätt, för basen över de komplexa heltal som ges av kolumnerna i matrisen nedan,

$${\begin{bmatrix}-2+2i&7+3i&7+3i&-5+4i\\3+3i&-2+ 4i&6+2i&-1+4i\\2+2i&-8+0i&-9+1i&-7+5i\\8+2i&-9+0i&6+3i&-4+4i\end{bmatrix}},$$

då ger kolumnerna i matrisen nedan en LLL-reducerad bas.

$${\begin{bmatrix}-6+3i&-2+2i&2-2i&-3+6i\\6-1i&3+3i&5-5i&2+1i\\2-2i&2+2i&-3-1i&-5+3i\ \-2+1i&8+2i&7+1i&-2-4i\\\end{bmatrix}}.$$

Genomföranden

LLL implementeras i

• Arageli som funktionen lll_reduction_int
• fpLLL som en fristående implementering
• FLINT som funktionen fmpz_lll
• GAP som funktionen LLLReducedBasis
• Macaulay2 som funktionen LLL i paketet LLLBases
• Magma som funktionerna LLL och LLLgram (tar en grammatris)
• Lönn som funktionen IntegerRelations[LLL]
• Mathematica som funktionen LatticeReduce
• Number Theory Library (NTL) som funktionen LLL
• PARI/GP som funktionen qflll
• Pymatgen som funktionen analys.get_lll_reduced_lattice
• SageMath som metoden LLL som drivs av fpLLL och NTL
• Isabelle/HOL i posten "arkiv av formella bevis" LLL_Basis_Reduction . Denna kod exporteras till effektivt körbar Haskell.

Se även

• Kopparsmedsmetod

Anteckningar

• Napias, Huguette (1996). "En generalisering av LLL-algoritmen över euklidiska ringar eller order" . Journal de Théorie des Nombres de Bordeaux . 8 (2): 387–396. doi : 10.5802/jtnb.176 .
•   Cohen, Henri (2000). En kurs i beräkningsalgebraisk talteori . GTM. Vol. 138. Springer. ISBN 3-540-55640-0 .
•   Borwein, Peter (2002). Beräkningsexkursioner i analys och talteori . ISBN 0-387-95444-9 .
• Luk, Franklin T.; Qiao, Sanzheng (2011). "En pivoterad LLL-algoritm" . Linjär algebra och dess tillämpningar . 434 (11): 2296–2307. doi : 10.1016/j.laa.2010.04.003 .
•   Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH (2008). En introduktion till matematisk kryptografi . Springer. ISBN 978-0-387-77993-5 .