One approach to factorization of positive integers
type: Item
instance of: scholarly article
title: One approach to factorization of positive integers
zbMATH Open document ID: 1254.11115
DOI: 10.3103/S1066369X11040037
author: A. A. Boiko
author: D. B. Ziyatdinov
author: Sh. T. Ishmukhametov
published in: Russian Mathematics
publication date: 2011-11-21T00:00:00Z
review text: This paper proposes a new variant of the Number Field Sieve (NFS). The Quadratic Sieve (QS) and NFS are the better known methods for factoring large integers \(N\),\, and many improvements and variants have been proposed. The NFS method see [\textit{A. K. Lenstra} and \textit{H. W. Lenstra}, The development of the number field sieve. Lecture Notes in Mathematics. 1554. Berlin: Springer-Verlag (1993; Zbl 0777.00017)] chooses an irreducible polynomial \(P(x)\)\, of small degree \(r\)\, (usually \(r=4,5,6\)), an integer \(m\)\, such that \(P(m)=N\)\, and a root \(\alpha\)\, of \(P(x)\)\, and try to factor expressions \(a+bm\)\, and \(a+b\alpha\)\, over a factor base of rational integers and a factor base of prime ideals of \(Q(\alpha)\). The proposed method does not require the use of the second base and consider only numbers \(a+bm\)\, such that \(a+bx\)\, is a quadratic residue modulo \(P(x)\). Section 1 summarizes the NFS method and Sections 2 and 3 describe the proposed new technique for \(r=2\)\, (and \(N=pq\),\, a RSA number) and give a toy example (\(N=4897\)). Finally Section 4 discusses the complexity of the method concluding that is the same as the complexity of the QS method. The Conclusion Section summarizes the main advantages of the proposed method but the authors point out that ``in practice one cannot use the irreducible polynomial of the degree \(r=2\)\, for factoring extremely large numbers; in solving this problem the NFS method is most efficient.''
Mathematics Subject Classification ID: 11Y05
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 5975527
zbMATH Keywords: factoring
zbMATH Keywords: quadratic sieve
zbMATH Keywords: number field sieve
zbMATH Keywords: RSA
reviewed by: Juan Tena Ayuso
MaRDI profile type: Publication
cites work: The development of the number field sieve
Recommended article: Q4036860
Recommended article: Q3117605
Recommended article: Q4273679
Recommended article: Square Root Algorithms for the Number Field Sieve
Recommended article: Q3838139
Recommended article: Q4343449
Recommended article: Q4273681
Recommended article: A one line factoring algorithm
Recommended article: Q4648972
Recommended article: Modifications to the number field sieve
description: scientific article; zbMATH DE number 5975527