Factorização de inteiros com a congruência de quadrados

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.