The quadratic sieve factoring algorithm

From MaRDI portal





[For the entire collection see Zbl 0578.00015.] At present, the best known factoring methods are Pomerance's quadratic sieve method (qsm) and Lenstra's elliptic curve method [ecm, cf. \textit{H. W. Lenstra} jun., Factoring integers with elliptic curves, preprint, Math. Inst. Univ. Amsterdam (1986; see the abstract below)]. This paper presents the basic ideas behind the quadratic sieve method and a number of improvements found by Davis and Holdridge, P. Montgomery and the author. The quadratic sieve method belongs to a large class of factoring algorithms, going back to \textit{M. Kraitchik} [Théorie des nombres. Tome II. Paris: Gauthier-Villars (1926)], which finds congruences \(U\equiv V\pmod N\), \(U\neq V\) (\(N\) is the number to be factorized), where \(U\) and \(V\) are completely (or partly) factorized. After finding sufficiently many congruences, one then tries to derive a special congruence: \(X^ 2\equiv Y^ 2\pmod N\) by multiplying a suitably chosen subset from the set of congruences \(U\equiv V\pmod N\). The greatest common divisor of \(X-Y\) and \(N\) often is a proper divisor of \(N\). If not, one should repeat the above procedure. The idea of the quadratic sieve is to choose \(U=(\lfloor \sqrt{N}\rfloor +A)^ 2\) and \(V=U-N\), where \(| A| \ll \lfloor \sqrt{n}\rfloor\). The numbers \(V\) can be quickly factorized with a quadratic sieve because of the special form of \(U\). In this paper the number \((10^{71}-1)/9\) is mentioned as the largest number cracked with the qsm (by Davis and Holdridge on a CRAY-XMP computer in about 9.5 hours). Since that achievement more practical experience with the quadratic sieve (and ecm) has been gained by R. Silverman, P. Montgomery, R. P. Brent, S. S. Wagstaff jun., W. Niebuhr, the reviewer and others [see \textit{J. Brillhart}, \textit{D. H. Lehmer}, \textit{J. L. Selfridge}, \textit{B. Tuckerman} and \textit{S. S. Wagstaff} jun., Factorizations of \(b^ n\pm 1\). Contemp. Math. 22 (1983; Zbl 0527.10001); updates to this book -- the fourth has appeared on July 3, 1986 -- can be obtained from S. S. Wagstaff jun.)]. Since the CPU-time of the ecm depends on the size of the smallest prime factor of the number to be factored whereas the CPU-time of the qsm depends on the size of the number to be factored, one should, with large numbers of size 80--100 digits (from which smaller prime divisors have been removed by trial and error, and e.g. by the so-called Pollard-Brent \(\rho\)-method), first try the ecm and, if ecm remains unsuccessful after sufficient time (to be determined experimentally), one should try the qsm next. This in turn could take much computer time, but already after a few minutes run of the qsm one can give a very precise estimate of the total amount of computer time needed to complete the qs run and factor \(N\). And this cannot be said about ecm!




Cited in
(33)








This page was built for publication: The quadratic sieve factoring algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3728066)