Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/25089
Title: Grafos de Ramanujan em teoria dos códigos e criptografia
Author: Cardoso, Gabriel Simões
Advisor: Almeida, Paulo José Fernandes
Pinheiro, Sofia Alexandra Marques Jorge
Keywords: Grafo expansor
Grafo de Ramanujan
Código LDPC
Função de síntese
Defense Date: 3-Aug-2018
Abstract: Nesta dissertação são estudadas propriedades de uma certa família de grafos, os grafos de Ramanujan. São ainda apresentadas e exemplificadas algumas aplicações destes, nomeadamente à Teoria dos Códigos e à Criptografia. Em particular, é apresentada e demonstrada uma propriedade dos grafos regulares com base no seu espetro, propriedade extremal para a família dos grafos de Ramanujan. Existindo outras construções possíveis, esta família pode ser construída, por exemplo, tal como é feito nesta dissertação, enquanto um caso particular de uma família de grafos de Cayley. Os grafos daquela família, caracterizando-se pelo facto de possuírem uma cintura grande, possibilitam, enquanto grafos expansores, a construção de códigos LDPC com uma grande distância e a construção de funções de síntese resistentes a colisões.
In this thesis are studied the properties of a certain family of graphs, the Ramanujan graphs, and are presented and exempli ed some of their applications, namely in Code Theory and Cryptography. Particularly, is presented and proved a regular graphs property based on their spectrum, which is extreme for the Ramanujan graphs family. There are many possible constructions for this family. In this thesis, the Ramanujan graphs are constructed as Cayley graphs. The graphs on that family, because of their large girth as expander graphs, are suitable to apply in constructions of LDPC codes and collision-resistant cryptographic hash functions.
URI: http://hdl.handle.net/10773/25089
Appears in Collections:DMat - Dissertações de mestrado
UA - Dissertações de mestrado

Files in This Item:
File Description SizeFormat 
Documento.pdf483.65 kBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.