Lecture Notes in Computer Science, 2007, Volume 4727/2007, 364-377, DOI: 10.1007/978-3-540-74735-2_25

CAIRN 2: An FPGA Implementation of the Sieving Step in the Number Field Sieve Method

Tetsuya Izu, Jun Kogure and Takeshi Shimoyama

View Related Documents

Abstract

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.

Fulltext Preview

Image of the first page of the fulltext document