Redução de bases de rede

Em matemática, a redução de bases de uma rede consiste em transformar qualquer base de uma rede em uma base quase ortogonal. Esse processo usa a noção de base fracamente reduzida.

Bases fracamente reduzidas

Uma base fracamente reduzida é uma base de rede cujos vetores são quase dois por dois ortogonais , no sentido de que, se fosse ortogonalizada usando o algoritmo de Gram-Schmidt , os coeficientes usados ​​para endireitar os vetores seriam menores, em valor absoluto aquele 1/2.

Mais formalmente: Seja uma base de rede, e a base ortogonal obtida graças a Gram-Schmidt , de modo que: B=(e1,...,enão){\ displaystyle B = (e_ {1}, ..., e_ {n})}B¯=(f1,...,fnão){\ displaystyle {\ overline {B}} = (f_ {1}, ..., f_ {n})}

feu=eeu-∑j=1eu-1noeu,jfj{\ displaystyle f_ {i} = e_ {i} - \ sum _ {j = 1} ^ {i-1} a_ {i, j} f_ {j}}, onde . noeu,j=<eeu,fj><fj,fj>{\ displaystyle a_ {i, j} = {\ dfrac {<e_ {i}, f_ {j}>} {<f_ {j}, f_ {j}>}}}

A base é ligeiramente reduzida quando para todos , . B{\ displaystyle B}eu,j{\ displaystyle i, j}|noeu,j|⩽12{\ displaystyle | a_ {i, j} | \ leqslant {\ dfrac {1} {2}}}

Notamos que se a base já fosse ortogonal, os coeficientes seriam todos zero. Intuitivamente, uma base ligeiramente reduzida corresponde a uma base ortogonal com uma precisão de 0,5. B{\ displaystyle B}noeu,j{\ displaystyle a_ {i, j}}

Baixa redução de bases

Na realidade, qualquer base de rede pode ser fracamente reduzida. Basta aplicar o algoritmo detalhado abaixo:

Entrée : une base de réseau B=(e1,...,en){\displaystyle B=(e_{1},...,e_{n})} Sortie : une base faiblement réduite issue de B{\displaystyle B} ReducFaible(B) : (f_1,...,f_n) = GramSchmidt(B) Pour tout (i,j){\displaystyle (i,j)} ai,j←<ei,fj><fj,fj>{\displaystyle a_{i,j}\leftarrow {\dfrac {<e_{i},f_{j}>}{<f_{j},f_{j}>}}} Si pour tout couple (i,j){\displaystyle (i,j)}, |ai,j|⩽12{\displaystyle |a_{i,j}|\leqslant {\dfrac {1}{2}}} retourne B Sinon Soit (i,j){\displaystyle (i,j)} le plus grand couple selon l'ordre lexicographique tel que |ai,j|>12{\displaystyle |a_{i,j}|>{\dfrac {1}{2}}} a←{\displaystyle a\leftarrow } l'entier le plus proche de ai,j{\displaystyle a_{i,j}} ei←ei−aej{\displaystyle e_{i}\leftarrow e_{i}-ae_{j}} retourne ReducFaible(B) Correção de algoritmo

Notamos a base obtida após a execução de um loop. B′=(e1′,...,enão′){\ displaystyle B '= (e' _ {1}, ..., e '_ {n})}

Nós temos . eeu′=eeu-noej=feu+∑k<eunoeu,kfk-nof,j-∑k<jnoj,kfk{\ displaystyle e '_ {i} = e_ {i} -ae_ {j} = f_ {i} + \ sum _ {k <i} a_ {i, k} f_ {k} -a_ {f, j} - \ sum _ {k <j} a_ {j, k} f_ {k}}

Vamos mostrar que casais maiores ou iguais a não representam um problema. (eu,j){\ displaystyle (i, j)}

Deixe ser a base obtida por Gram-Schmidt em . Observam-se os coeficientes resultantes da ortogonalização. (f1′,...,fnão′){\ displaystyle (f '_ {1}, ..., f' _ {n})}B′{\ displaystyle B '}nok,eu′{\ displaystyle a '_ {k, l}}

Temos para todos e para todos , . k≠eu{\ displaystyle k \ neq i}eu{\ displaystyle l}nok,eu′=nok,eu{\ displaystyle a '_ {k, l} = a_ {k, l}}

Caso contrário, quando , se também tivermos . k=eu{\ displaystyle k = i}eu>j{\ displaystyle l> j}noeu,eu′=noeu,eu{\ displaystyle a '_ {i, l} = a_ {i, l}}

Finalmente, nos outros casos ,. noeu,eu′=noeu,eu-vsnoj,eu{\ displaystyle a '_ {i, l} = a_ {i, l} -ca_ {j, l}}

Os para os pares maiores estritamente do que não são modificados, portanto, são sempre de valor absoluto inferior a 1/2. Além disso,nok,eu{\ displaystyle a_ {k, l}}(eu,j){\ displaystyle (i, j)}|noeu,j′|noeu,j-no|⩽12{\ displaystyle | a '_ {i, j} | a_ {i, j} -a | \ leqslant {\ dfrac {1} {2}}}  

Bases reduzidas

Diz-se que uma base de rede é reduzida quando é fracamente reduzida e satisfaz a seguinte propriedade: B=(e1,...,enão){\ displaystyle B = (e_ {1}, ..., e_ {n})}

Se for a ortogonalização de Gram-Schmidt de coeficientes , devemos ter: (f1,...,fnão){\ displaystyle (f_ {1}, ..., f_ {n})}B{\ displaystyle B}noeu,j{\ displaystyle a_ {i, j}}

||feu+1+noeu+1,eufeu||2⩾34||feu||2{\ displaystyle || f_ {i + 1} + a_ {i + 1, i} f_ {i} || ^ {2} \ geqslant {\ dfrac {3} {4}} || f_ {i} || ^ {2}}

Os algoritmos a seguir mostram que qualquer base pode ser reduzida ao tempo polinomial.

Algoritmo	Nome completo	Ano de publicação	Implementação
EU VOU	Lenstra Lenstra Lovász	1982	NTL  (en) (en) "  fpll (link do Github)  "
BKZ	Bloco Korkin Zolotarev	1987	NTL  (en) (en) "  fpll (link do Github)  "
RSR	Redução de Amostragem Aleatória	2002
PDR	Redução Dupla Primária	2002

Referências

1. Redução de malha  (in)
2. Abuaf Roland e Boyer Ivan, " Factorization inZ[X]{\ displaystyle \ mathbb {Z} [X]}  ", palestra  do Mestre proposta por François Loeser ,20 de junho de 2007( leia online )
3. (em) Hanrot William, "  Worst-Case Hermit-Korkine-Zolotarev Reduced Lattice Basics  " , arXiv: 0801.3331 [math.NT] ,2008( leia online )

Artigos relacionados

• Rede (geometria)
• Algoritmo LLL

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">