Algoritmo LLL

O algoritmo LLL , iniciais de A. Lenstra , H. Lenstra e L. Lovász , é um algoritmo de redução de rede que roda em tempo polinomial .

Apresentação

O algoritmo LLL executa a redução da base da rede . Ele toma como entrada um número d de vetores de base de uma rede , de modo que esses vetores sejam de dimensão ne de norma menor que B , e retorna como saída uma base de rede reduzida de LLL, ou seja, quase ortogonal , no tempo . $O (d ^ {5} n \ log ^ {3} B) \,$

Pseudo-código

O algoritmo LLL é baseado no algoritmo de redução de base fraca , o que torna uma base quase ortogonal.

Entrée : Une base

B=(e_{1},...,e_{n})

Sortie : Une base réduite issue de

B

LLL(B): B =

(e_{1},...,e_{n})\leftarrow

ReducFaible(B) *On fait Gram-Schmidt* Pour i=1 à n : Pour j= 1 à i-1 :

a_{i,j}\leftarrow {\dfrac {<e_{i},e_{j}>}{<e_{j},e_{j}>}}

e_{i}\leftarrow e_{i}-\sum _{j<i}a_{i,j}e_{j}

Si B est réduite retourne B Sinon

i\leftarrow min(\lbrace ||j\in [1,n]~|~e_{j}+a_{j+1,j}e_{j+1}||^{2}<{\dfrac {3}{4}}||e_{j}||^{2}\rbrace )

echanger(

e_i

e_{i+1}

) retourne LLL(B)

Formulários

Originalmente, as aplicações consistiam na produção de um algoritmo para fatoração de polinômios com coeficientes racionais em produtos de polinômios irredutíveis, bem como na resolução de problemas de otimização linear com soluções inteiras e dimensões fixas. Outras aplicações foram descobertas em criptografia , especialmente em criptografia de chave pública , por exemplo com RSA , criptossistemas baseados no problema de mochila e NTRUEncrypt . Em particular, o algoritmo LLL tornou todos os criptossistemas usando o problema da mochila ineficientes. Também é usado no caso de redes euclidianas .

Notas e referências

(pt) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado “ Lenstra - Lenstra - algoritmo de redução da base da rede de Lovász ” ( ver lista de autores ) .

Abderrahmane Nitaj, “ Aplicações do algoritmo LLL em criptografia ” , no Departamento de Matemática e Mecânica da Universidade de Caen Basse Normandie (UCBN) .
Pascal Boyer, pequeno companheiro dos números e suas aplicações , Paris / 58-Clamecy, Calvage e Mounet,2019, 648 p. ( ISBN 978-2-916352-75-6 ) , VI. Criptografia, cap. 6 (“O método da mochila”), p. 538-539.

Bibliografia

(en) A. Lenstra, H. Lenstra e L. Lovász, “ Factoring polinômios com coeficientes racionais ” , Mathematische Annalen , vol. 261, n o 4,1982, p. 515-534 ( DOI 10.1007 / BF01457454 , leia online )Link Resenhas de matemática
(pt) Peter Borwein , Computational Excursions in Analysis and Number Theory, Springer, 2002 ( ISBN 978-0-387-95444-8 ) : contém uma descrição completa dos algoritmos, bem como algumas implementações de pseudocódigo
Abuaf Roland, Boyer Ivan, “ Factorisation dans ${\ displaystyle \ mathbb {Z} [X]}$ ”, palestra do Mestre proposta por François Loeser ,20 de junho de 2007( leia online )