The quadratic sieve factoring algorithm
[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!
- On the distribution in short intervals of integers having no large prime factor
- Factoring RSA moduli with primes sharing bits in the middle
- Use of SIMD-based data parallelism to speed up sieving in integer-factoring algorithms
- Approximate short vectors in ideal lattices of \(\mathbb{Q}(\zeta_{p^e})\) with precomputation of \({\mathrm {Cl}}(\mathcal{O}_K)\)
- Factoring with the quadratic sieve on large vector computers
- Mathematical problems in cryptology
- Index calculation attacks on RSA signature and encryption
- On computing ord\(_{N}(2)\) and its application
- Recovering Fourier coefficients of some functions and factorization of integer numbers
- Factorization using binary decision diagrams
- Post-quantum cryptography: state of the art
- Factoring multi-power RSA moduli with primes sharing least or most significant bits
- Practical cryptanalysis of ISO 9796-2 and EMV signatures
- Running Time Predictions for Factoring Algorithms
- Smooth numbers and the quadratic sieve
- The Multiple Polynomial Quadratic Sieve
- A Pipeline Architecture for Factoring Large Integers with the Quadratic Sieve Algorithm
- scientific article; zbMATH DE number 17387 (Why is no real title available?)
- On sharp transitions in making squares
- scientific article; zbMATH DE number 708815 (Why is no real title available?)
- scientific article; zbMATH DE number 2162228 (Why is no real title available?)
- Factorization using the quadratic sieve algorithm
- Forty years of attacks on the RSA cryptosystem: a brief survey
- Some arithmetical properties on hyperbola
- Using LLL-reduction for solving RSA and factorization problems
- Generation of Elements with Small Modular Squares and Provably Fast Integer Factoring Algorithms
- scientific article; zbMATH DE number 2230939 (Why is no real title available?)
- On the number of semismooth integers
- Supersingular j-invariants and the class number of ℚ(−p)
- An integrated parallel GNFS algorithm for integer factorization based on linbox montgomery block Lanczos method over GF(2)
- Computational Number Theory, Past, Present, and Future
- Factoring multi power RSA moduli with a class of secret exponents
- Efficient verification of Tunnell's criterion
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)