The hardness of the integer factorization problem assures the security of some public-key cryptosystems including RSA, and
the number field sieve method (NFS), the most efficient algorithm for factoring large integers currently, is a threat for
such cryptosystems. Recently, dedicated factoring devices attract much attention since it might reduce the computing cost
of the number field sieve method. In this paper, we report implementational and experimental results of a dedicated sieving
device “CAIRN 2” with Xilinx’s FPGA which is designed to handle up to 768-bit integers. Used algorithm is based on the line
sieving, however, in order to optimize the efficiency, we adapted a new implementational method (the pipelined sieving). In
addition, we actually factored a 423-bit integer in about 30 days with the developed device CAIRN 2 for the sieving step and
usual PCs for other steps. As far as the authors know, this is the first FPGA implementation and experiment of the sieving
step in NFS.
Keywords Integer factorization - the number field sieve method (NFS) - the sieving step - implementation - FPGA
A part of this research is financially supported by a contract research with the National Institute of Information and Communications
Technology (NICT), Japan.