Please use this identifier to cite or link to this item: http://hdl.handle.net/10773/10546
Title: Factorização de inteiros com a congruência de quadrados
Author: Custódio, Bruno Miguel Santos Pinto Marques
Advisor: Almeida, Paulo José Fernandes
Keywords: Matemática aplicada
Factorização (Matemática)
Fracções contínuas
Defense Date: 2010
Publisher: Universidade de Aveiro
Abstract: Qualquer número inteiro n ímpar e composto pode ser escrito como diferença dos quadrados de dois outros números inteiros. Desta forma, se conhecermos estes inteiros podemos facilmente factorizar n. No entanto, e embora simples e engenhosa, esta ideia frequentemente utilizada por Pierre de Fermat para factorizar números pequenos apresenta alguns problemas quando o tamanho dos inteiros a factorizar aumenta. Deste modo, torna-se mais fácil e portanto preferível escrever não n mas sim um seu qualquer múltiplo como diferença de dois quadrados, os quais, na maior parte dos casos, nos permitem de igual forma factorizar n. Esta pequena modificação à ideia de Fermat, designada por congruência de quadrados, está por detrás de um grande número de algoritmos de factorização modernos como o “método das fracções contínuas”, o “crivo quadrático” e o “crivo dos corpos de números”. Nesta dissertação estudamos cada um destes algoritmos e alguns dos seus melhoramentos em detalhe, apresentando alguns exemplos demonstrativos do seu funcionamento.
Every odd and composite integer n may be written as a difference of the squares of two other integers. Thus, if we know these integers we may easily factor n. However, simple and ingenious as it may be, this idea often used by Pierre de Fermat to factor small numbers begins to lose its efficiency as the size of the integers being factored gets larger. That being, it becomes easier and thus preferable to write not n but any of its multiples as a difference of two squares, which, most of the times, allow us to factor n as well. This small modification to Fermat’s idea, called the quadratic congruence method, lies behind a large number of modern factorization algorithms, such as the “continued fractions method”, the “quadratic sieve” and the “number field sieve”. In this dissertation we study each of these algorithms and some of their improvements in detail, and present some examples of their application.
Description: Mestrado em Matemática e Aplicações
URI: http://hdl.handle.net/10773/10546
Appears in Collections:DMat - Dissertações de mestrado
UA - Dissertações de mestrado

Files in This Item:
File Description SizeFormat 
6511.pdf1.16 MBAdobe PDFView/Open


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

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