| Resumo: | 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.
|
|---|