Utilize este identificador para referenciar este registo:
http://hdl.handle.net/10773/25089
Título: | Grafos de Ramanujan em teoria dos códigos e criptografia |
Autor: | Cardoso, Gabriel Simões |
Orientador: | Almeida, Paulo José Fernandes Pinheiro, Sofia Alexandra Marques Jorge |
Palavras-chave: | Grafo expansor Grafo de Ramanujan Código LDPC Função de síntese |
Data de Defesa: | 3-Ago-2018 |
Resumo: | 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 |
Aparece nas coleções: | UA - Dissertações de mestrado DMat - Dissertações de mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Documento.pdf | 483.65 kB | Adobe PDF | Ver/Abrir |
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.