Abstract
Factorization of positive integers into primes is a hard computational task. Its complexity lies in the base of the most popular method of cryptography, the RSA method. In this paper we propose a new technique in a factorization procedure which combines ideas of the Number Field Sieve (NFS) and the Quadratic Sieve (QS) in a special manner.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
C. Pomerance, “Smooth Numbers and the Quadratic Sieve,” Algorithmic Number Theory, Cambridge, MSRI publication 44, 69–82 (2008).
M. E. Briggs, “An Introduction to the General Number Field Sieve,” Master’s Thesis (Virginia Polytechnic Institute and State University, Blacksburg, Virginia, 1998).
A. Lenstra and H. Lenstra (Eds.), The Development of the Number Field Sieve, Lecture Notes in Math. 1554 (Springer-Verlag, Berlin, 1993).
H. Boender, The Number of Relations in the Quadratic Sieve Algorithm, Report W96-21 (Leiden University, 1996).
A. V. Cheremushkin, Lectures on Arithmetic Algorithms in Cryptography (MTsMNO, Moscow, 2002) [in Russian].
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © A.A. Boiko, D.B. Ziyatdinov, Sh.T. Ishmukhametov, 2011, published in Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2011, No. 4, pp. 15–22.
About this article
Cite this article
Boiko, A.A., Ziyatdinov, D.B. & Ishmukhametov, S.T. One approach to factorization of positive integers. Russ Math. 55, 12–17 (2011). https://doi.org/10.3103/S1066369X11040037
Received:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S1066369X11040037