On General Number Field Sieve and its Polynomial Selection

Abstract:

This paper analyzes the algorithm of general number field sieve and suggesting some ofits solving in the problem of larger integers factorization. And a design of its implementation via thelibrary GMP for polynomial selection is discussed. Our work has the advantages of easy extensionsto various applications such as RSA, Discrete logarithm problems, Primality testing and so on.

• Periodical: Applied Mechanics and Materials (Volumes 519-520)
• Pages: 250-256
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.519-520.250
• Online since: February 2014
• Authors: Gang Zhou*
• Keywords: GMP, GNFS(General Number Field Sieve), Number Field Sieve (NFS), RSA, Special Number Field Sieve (SNFS)

References

[1] RSA, www. thersa. org.

[2] Lenstra, A. K., Lenstra, H. W. Jr. , The Development of the Number Field Sieve, Berlin: SpringerVerlag, (1993).

[3] Andrea Pellegrini, Valeria Bertacco, Todd Austin, Fault-Based Attack of RSA Authentication, (2010).

[4] Gordon D. M., Discrete logarithms in GF(p) Using the Number Held Sieve, SIAM J. Discrete Math. 6 (1993), 124-138.

DOI: 10.1137/0406010

[5] Adleman L. M., Factoring numbers using singular integers, Proc, 23rd Annual ACM Symp on Theory of Computing (STOC), New Orleans, May 6-8, 1991, 64-71.

DOI: 10.1145/103418.103432

[6] Buchman J., Loho J., Zayer J., An Implementation of Number Field Sieve, in Douglas R. Stinson (Ed. ), Advances in Cryptology-CRYPT0'93, 13th Annual International Cryptology Conference Santa Barbara, California, USA Proceedings August 22-26, 1993, pp.159-165, Berlin: SpringerVerlag, (1994).

DOI: 10.1007/3-540-48329-2

[7] kmGNFS, kmGNFS-A General Number Field Sieve (GNFS) Implementation, kmgnfs. cti. gr.

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

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

[9] Marije Elkenbracht-Huizing, An Implementation of the Number Field Sieve, Experimental Mathematics, Vol. 5 (1996), No. 3.

DOI: 10.1080/10586458.1996.10504590

[10] Sashisu Bajracharya, Deapesh Misra, Kris Gaj, Tarek El-Ghazawi, Reconfigurable Hardware Implementation of Mesh Routing in the Number Field Sieve Factorization.

DOI: 10.1109/fpt.2004.1393277

[11] Paul Zimmermann, CADO-NFS: An Implementation of The Number Field Sieve, (2008).

[12] Thorsten Kleijung, On Polynomial Selection for the Genral Number Number Fieve Sieve, Mathematics of Computation Volume 75, Number 256, October 2006, Pages 2037�C2047.

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

[13] THORSTEN KLEINJUNG, Kazumaro Aoki, Jens Franke, Arjen K. Lenstra, et al, Factorization of a 768-bit RSA modulus, (2010).

[14] Namhun Koo, Gooc Hwa Jo, Soonhak Kwon, On Nonlinear Polynomial Selection and Geometric Progression (modN) for Number Field Sieve, preprint, (2011).

[15] T. Prest, and P. Zimmermann, Non-linear Polynomial Selection for the Number field Sieve, (2010).

[16] Cado-NFS, cado-nfs. gforge. inria. fr, Berlin: Springer-Verlag, (1993).

[17] Min yang, Qingshu Meng, Zhangyi Wang, Lina Wang, Huanguo Zhang, Polynomial Selection for the Number Field Sieve in Geometric View, Cryptology ePrint Archive: Report 2013/583.

[18] Jeff Gilchrist, Beginners Guide to NFS factoring using GGNFS and MSIEVE with the factmsieve. pl perl script, gilchrist. ca.

[19] Sage, Quadratic Sieve, www. sagemath. org.

[20] Laurence T. Yang, Li Xu, Man Lin, John Quinn, A Parallel GNFS Algorithm Based on a Reliable Look-Ahead Block Lanczos Method for Integer Factorization, in: Embedded and Ubiquitous Computing Lecture Notes in Computer Science Volume 4096, 2006, pp.110-120.

DOI: 10.1007/11802167_13

[21] Greg Childers, Factorization of a 1061-bit number by the Special Number Field Sieve, (2012).