Métodos de factorização em números primos

Abstract

A factorizaçao de números inteiros é um dos grandes temas de estudo da Teoria dos Números. Actualmente uma das razões do interesse por este tema deve-se à possível existência de métodos efcientes de factorização, que comprometam a segurançaa dos sistemas criptográficos de chave pública, como, por exemplo, o RSA [1]. O Crivo Quadrático é considerado um dos métodos mais importantes da actualidade a factorizar números inteiros, [4, pag. 169] pois é um dos mais poderosos. Este trabalho tem como objectivo o estudo do método RSA, onde veremos as técnicas que permitem encontrar os factores primos de n, e, para terminar, perceber se o método do Crivo Quadrático é ou não eficiente na quebra da cifra RSA. Para tal, necessitaremos também de estudar diversos conceitos matemáticos envolvidos no tema.

The integers factorization is one of the most important study subject in Number's Theory. Nowadays the concern for this issue exists due to the possible existence of efficient factorization methods, which compromises the security of public key cryptosystems, e.g., the RSA method [1]. The Quadratic Sieve method is considered, in our days, one of the most important methods to factor integers [4, pag. 169], because it is one of the most powerful. This document aims to study the RSA method, where we look at techniques for finding the prime factors of n, and finally, realize that the method Quadratic Sieve is or is not effective in breaking the RSA cipher. To such, we need also to study various mathematical concepts involved in the issue.