One approach to factorization of positive integers (Q647854): Difference between revisions

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.''