Fatoração de números inteiros usando curvas elíticas

Abstract

O problema da fatoração inteira tem obtido considerável atenção por sua utilização ao em sistemas criptográficos modernos que têm sua segurança baseada na dificuldade de fatorar números grandes. Neste trabalho, apresentamos a descrição de um método de fatoração de números inteiros, o Método das Curvas Elíticas (Elliptic Curve Method - ECM) devido a H. W. Lenstra [Len87], que usa curvas elíticas. Ele é baseado num outro método de fatoração, o método p−1 de Pollard [Pol74]. O método de Pollard utiliza a estrutura do grupo multiplicativo Z*p, enquanto o ECM utiliza a estrutura de grupo dos pontos de uma curva elítica.

The Integer Factoring Problem has obtained considerable attention for its utilization in modern cryptographic systems which have its security based on the difficulty of factoring large numbers. In this work, we present the description of a method for integer factorization, the Elliptic Curve Method - ECM, invented by H. W. Lenstra [Len87], which uses elliptic curves. It is based on another method for integer factorization, the Pollard p − 1 method [Pol74]. The Pollard p − 1 method uses the structure of the multiplicative group Z*p, while the Elliptic Curve Method uses the group structure of the points of an elliptic curve.