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: | UA - Dissertações de mestrado DMat - Dissertações de mestrado |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.