Please use this identifier to cite or link to this item: http://hdl.handle.net/1822/30314

TitleParalelização de algoritmos de enumeração para o problema do vector mais curto em sistemas de memória partilhada e distribuída
Author(s)Correia, Fábio José Gonçalves
Mariano, Artur Miguel Matos
Proença, Alberto José
KeywordsPVC
Enumeração
Paralelização
OpenMP
MPI
Issue dateSep-2014
Abstract(s)A criptografia baseada em retículos tem vindo a tornar-se um tópico central ao longo da última década, uma vez que se acredita que este tipo de criptografia seja resistente a ataques infligidos com computadores quânticos. A segurança desta criptografia é medida pela eficácia e praticabilidade dos algoritmos que resolvem problemas centrais em retículos, como o problema do vector mais curto (PVC), e é, por isso, importante determinar qual o desempenho máximo destes algoritmos em arquitecturas computacionais de alto rendimento. Neste sentido, este artigo apresenta, pela primeira vez, um estudo detalhado sobre o desempenho dos dois mais promissores algoritmos de resolução do PVC, o ENUM e uma variante eficiente da enumeração de Schnorr-Euchner, com e sem poda extrema. Em particular, são propostas versões paralelas destes algoritmos, desenvolvidas para óptimo balanço de carga e, consequentemente, melhor desempenho. Conduziu-se uma extensa série de testes, quer em memória partilhada, para as variantes sem poda, quer em memória distribuída, para as variantes com poda. Os resultados mostram que as implementações em memória partilhada atingem, em certos casos, acelerações lineares até 16 \textit{threads}. As implementações em memória distribuída, por seu turno, são aceleradas em cerca de 13 vezes para 16 processos, permitindo a resolução do PVC em retículos em dimensão 80 em menos de 250 segundos.
TypeconferencePaper
URIhttp://hdl.handle.net/1822/30314
Peer-Reviewedyes
AccessopenAccess
Appears in Collections:DI/CCTC - Artigos (papers)
CCTC - Artigos em atas de conferências internacionais (texto completo)

Files in This Item:
File Description SizeFormat 
Inforum14.pdfDocumento Principal416,34 kBAdobe PDFView/Open

Partilhe no FacebookPartilhe no TwitterPartilhe no DeliciousPartilhe no LinkedInPartilhe no DiggAdicionar ao Google BookmarksPartilhe no MySpacePartilhe no Orkut
Exporte no formato BibTex mendeley Exporte no formato Endnote Adicione ao seu Currículo DeGóis