Calculation Components Analysis of the Lattice Sieve

Yang Yang; Guang Zeng; Zheng Wang; Wen Bao Han

doi:10.4028/www.scientific.net/AMR.466-467.298

Paper Titles

Event-Based Modeling of Essential Medicines Selection with Numerical Material
p.277

Structural Optimization Research of Composite Aircraft Based on Different Wing Stiffness Constraints
p.282

Research on Characteristics and Three-Dimension Geologic Model Building of the Chang2 Reservoir, Yanchang Formation in Zhifang Area, Zhidan Oilfield
p.287

Synthesis, Characterization, and DFT of a Novel Reactive Phosphorus Flame Retardant
p.293

Calculation Components Analysis of the Lattice Sieve
p.298

Research on Three-Dimension Sedimentary Facies Model Building of the Reservoir Chang2 Member, Yanchang Formation in Zhifang Area, Erdos Basin
p.303

Application of Decision Tree Algorithm in Lumber Hierarchies
p.308

Efficient Simulation of Grain Burning Surface Regression
p.314

Synthesis of n-Butyl Salicylate Catalyzed by Boric Acid
p.319

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 466-467Calculation Components Analysis of the Lattice...

Calculation Components Analysis of the Lattice Sieve

Abstract:

Currently, the best known algorithm for factoring RSA modulus is the General Number Field Sieve. Through the software optimized implementation of GNFS with RSA-768, we extracted nine main calculation components from the lattice sieve. Detail descriptions and comprehensive analysis of the properties about calculation, memory and communication to the nine components were given in this paper, which makes it possible to use of a variety of computing platforms, such as CPU, FPGA, CELL, and GPU etc, to accelerate the realization of GNFS.

You might also be interested in these eBooks

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 466-467)

Pages:

298-302

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.466-467.298

Citation:

Cite this paper

Online since:

February 2012

Authors:

Yang Yang, Guang Zeng, Zheng Wang, Wen Bao Han

Keywords:

Calculation Component, GNFS, High Performance Computing, Lattice Sieve

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] J.P. Buhler, H.W. Lenstra, Jr.,C. Pomerance. Factoring integers with the number field sieve. LNCS 1554 in Lecture Notes in Mathematics, pp.50-94. Springer-Verlag, (1993).

DOI: 10.1007/bfb0091539

Google Scholar

[2] A.K. Lenstra, H.W. Lenstra, Jr. M. S. Manasse, J. M. Pollard. The Factorization of ninth Fermat Number, Math. Comp. 61, (1993).

DOI: 10.1090/s0025-5718-1993-1182953-4

Google Scholar

[3] J. M. Pollard. The Lattice Sieve. In Arjen K. Lenstra and Hendrik W. Lenstra, Jr., editors, The development of the number field sieve, number 1554 in Lecture Notes in Mathematics, pp.43-49. Springer-Verlag, (1993).

DOI: 10.1007/bfb0091537

Google Scholar

[4] Brian Antony Murphy. Polynomial Selection for the Number Field Sieve Integer Factorisation Algorithm. A Thesis submitted for the degree of doctor of philosophy of the Australian National university, July, (1999).

Google Scholar

[5] S. Cavalla. Strategies filtering in the number field sieve. MAS-R0012 MAY 31, (2000).

Google Scholar

[6] Peter L. Montgomery. A block Lanczos algorithm for finding dependencies over GF(2). In Advanced in Cryptology-Eurocrypt'95, LNCS 921, pages 106-120, Springer-Verlag, Berlin, (1995).

DOI: 10.1007/3-540-49264-x_9

Google Scholar

[7] Phong Nguyen. A Montgomery-Like Square Root for the Number Field Sieve. Ecole Normale Superieure Laboratoire d'Informatique 45, rue d'Ulm.

Google Scholar

[8] Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, et al, Factorization of a 512-bit RSA modulus. In Advances in EUROCRYPT'00, p.118. Springer, Berlin, (2000).

Google Scholar

[9] Thorsten Kleinjung , On polynomial selection for the gereral number field sieve, Math. Comput. , vol. 75, no. 256, pp.2037-2047, (2006).

DOI: 10.1090/s0025-5718-06-01870-9

Google Scholar

[10] Peter L. Montgomery, Searching for Higher-Degree Polynomials for the General Number Field Sieve. Microsoft Research, USA, and CWI October, (2006).

Google Scholar

[11] Jens Franke, Thorsten Kleinjung, Continued fractions and lattice sieving. proc. Workshop on Special Purpose Hardware for Attacking Cryptographic Systems (SHARCS) 2005, February (2005).

Google Scholar