Made available in DSpace on 2014-06-12T18:31:41Z (GMT). No. of bitstreams: 2 arquivo8516_1.pdf: 556858 bytes, checksum: 61691f022e165231e3147bd9b1b11a63 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2003 / Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiência na suposição de que, em termos práticos, é impossível fatorar números inteiros suficientemente grandes em uma escala de tempo aceitável. Mais precisamente, não existem, até o momento, algoritmos de fatoração em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dígitos binários do número a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoração que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quântico para fatorar um número inteiro de tamanho arbitrário. Esse algoritmo ao invés de abordar o problema de decompor tal número em dois fatores não triviais pelo método direto de divisões sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o número fatorado, onde esse inteiro é escolhido aleatoriamente relativamente primo com o número fatorado. Shor faz uso de um algoritmo quântico para calcular essa ordem. A computação quântica revela um paradigma computacional bastante adverso da computação clássica. Enquanto esta última é realizada através de operações binárias determinísticas com base na lógica booleana clássica, a computação quântica fundamenta as suas operações nos postulados que descrevem o comportamento quântico da matéria. Portanto, é probabilística no seu modus operandi. Essa diferença entre os formalismos lógicos da computação clássica e da computação quântica é um reflexo direto da natureza dos sistemas físicos que são utilizados para implementar concretamente cada uma dessas computações. Esta dissertação apresenta o algoritmo de Shor para fatoração em um computador quântico. Na seqüência, introduzimos no capítulo 1 alguns conceitos básicos da computação clássica com o objetivo de criar um ambiente de idéias favorável à apresentação da computação quântica como uma extensão, tão natural quanto possível, do modelo clássico computacional. Assim, no capítulo 2, apresentamos as bases do formalismo matemático que modela a computação quântica, atendo-nos apenas aos aspectos conceituais que são, direta ou indiretamente, aplicados na descrição do algoritmo de Shor. Os capítulos 3 e 4 são dedicados à apresentação do algoritmo de fatoração de Shor, feita em duas partes. A primeira diz respeito a parte não quântica e aborda os aspectos algébricos do algoritmo. Também é demonstrado o teorema que assegura a viabilidade probabilística da solução desse problema. No capítulo 4, apresentamos a parte quântica do algoritmo de Shor. O ponto alto da dissertação é alcançado mostrando-se como encontrar a ordem de um inteiro módulo o número a ser fatorado relativamente primo com este, conciliando o algoritmo quântico com uma interpretação clássica de seus dados de saída, mediante o uso da expansão de um número racional em frações contínuas

Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2016-12-12T16:55:40Z No. of bitstreams: 2 Tese - Jesmmer da Silveira Alves - 2016.pdf: 4498358 bytes, checksum: e1a92f88800ddd8032e2b0c1039f216d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Jaqueline Silva (jtas29@gmail.com) on 2016-12-13T19:31:42Z (GMT) No. of bitstreams: 2 Tese - Jesmmer da Silveira Alves - 2016.pdf: 4498358 bytes, checksum: e1a92f88800ddd8032e2b0c1039f216d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2016-12-13T19:31:42Z (GMT). No. of bitstreams: 2 Tese - Jesmmer da Silveira Alves - 2016.pdf: 4498358 bytes, checksum: e1a92f88800ddd8032e2b0c1039f216d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-11-18 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Quadratic forms are algebraic expressions that have important role in different areas of computer science, mathematics, physics, statistics and others. We deal with rational quadratic forms and integral quadratic forms, with rational and integer coefficients respectively. Existing methods for recognition of rational quadratic forms have exponential time complexity or use approximation that weaken the result reliability. We develop a polinomial algorithm that improves the best-case of rational quadratic forms recognition in constant time. In addition, new strategies were used to guarantee the results reliability, by representing rational numbers as a fraction of integers, and to identify linear combinations that are linearly independent, using Gauss reduction. About the recognition of integral quadratic forms, we identified that the existing algorithms have exponential time complexity for weakly nonnegative type and are polynomial for weakly positive type, however the degree of the polynomial depends on the algebra dimension and can be very large. We have introduced a polynomial algorithm for the recognition of weakly nonnegative quadratic forms. The related algorithm identify hypercritical restrictions testing every subgraph of 9 vertices of the quadratic form associated graph. By adding Depth First Search approach, a similar strategy was used in the recognition of weakly positive type. We have also shown that the recognition of integral quadratic forms can be done by mutations in the related exchange matrix. / Formas quadráticas são expressões algébricas que têm papel importante em diferentes áreas da ciência da computação, matemática, física, estatística e outras. Abordamos nesta tese formas quadráticas racionais e formas inteiras, com coeficientes racionais e inteiros respectivamente. Os métodos existentes para reconhecimento de formas quadráticas racionais têm complexidade de tempo exponencial ou usam aproximações que deixam o resultado menos confiável. Apresentamos um algoritmo polinomial que aprimora o melhorcaso do reconhecimento de formas quadráticas para tempo constante. Ainda mais, novas estratégias foram usadas para garantir a confiabilidade dos resultados, representando nú- meros racionais como frações de inteiros, e para identificar combinações lineares que são linearmente independentes, usando a redução de Gauss. Sobre o reconhecimento de formas inteiras, identificamos que os algoritmos existentes têm complexidade de tempo exponencial para o tipo fracamente não-negativa e polinomial para o tipo fracamente positiva. No entanto, o grau do polinômio depende da dimensão da álgebra e pode ser muito grande. Apresentamos um algoritmo polinomial para o reconhecimento de formas inteiras fracamente positivas. Este algoritmo identifica restrições hipercríticas avaliando todo subgrafo com 9 vértices do grafo associado à forma inteira. Através da busca em profundidade, uma estratégia similar pôde ser usada no reconhecimento do tipo fracamente positiva. Por fim, mostramos que o reconhecimento de formas inteiras pode ser feito através de mutações na matriz de troca relacionada.