Quadratic sieve

The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve. It is a general-purpose factorization algorithm, meaning that its running time depends solely on the size of the integer to be factored, and not on special structure or properties. It was invented by Carl Pomerance in 1981 as an improvement to Schroeppel's linear sieve. Basic aim The algorithm attempts to set up a congruence of squares modulo n (the integer to be factorized), which often leads to a factorization of n. The algorithm works in two phases: the data collection phase, where it collects information that may lead to a congruence of squares; and the data processing phase, where it puts all the data it has collected into a matrix and solves it to obtain a congruence of squares. The da

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (9)

Related publications

Related people (1)

Related people

Related units (1)

Related units

Related concepts (8)

Related concepts

Related courses (2)

Related courses

Related lectures (2)

Related lectures

Integer factorization

In number theory, integer factorization is the decomposition, when possible, of a positive integer into a product of smaller integers. If the factors are further restricted to be prime numbers, the

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. F

General number field sieve

In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than 10100. Heuristically, its complexity for factoring an intege

MATH-489: Number theory in cryptography

The goal of the course is to introduce basic notions from public key cryptography (PKC) as well as basic number-theoretic methods and algorithms for cryptanalysis of protocols and schemes based on PKC.

EE-611: Linear system theory

The course covers control theory and design for linear time-invariant systems : (i) Mathematical descriptions of systems (ii) Multivariables realizations; (iii) Stability ; (iv) Controllability and Observability; (v) Minimal realizations and coprime fractions; (vi) Pole placement and model matching.

Analysis and optimization of the TWINKLE factoring device

Arjen Lenstra

We describe an enhanced version of the TWINKLE factoring device and analyse to what extent it can be expected to speed up the sieving step of the quadratic Sieve and number field Sieve factoring algorithms. The bottom line of our analysis is that the TWINKLE-assisted factorization of 768 bit numbers is difficult but doable in about 9 months (including the sieving and matrix parts) by a large organization which can use 80000 standard Pentium II PC's and 5000 TWINKLE devices

2000

A world wide number field sieve factoring record: on to 512 bits

Arjen Lenstra

We present data concerning the factorization of the 130-digit number RSA130 which we factored on April 10, 1996, using the number field sieve factoring method. This factorization beats the 129-digit record that was set on April 2, 1994, by the quadratic sieve method. The amount of computer time spent on our new record factorization is only a fraction of what was spent on the previous record. We also discuss a World Wide Web interface to our sieving program that we have developed to facilitate contributing to the sieving stage of future large scale factoring efforts. These developments have a serious impact on the security of RSA public key cryptosystems with small moduli. We present a conservative extrapolation to estimate the difficulty of factoring 512-bit numbers

1996

On the factorization of RSA-120

Arjen Lenstra

We present data concerning the factorization of the 120-digit number RSA-120, which we factored on July 9, 1993, using the quadratic sieve method. The factorization took approximately 825 MIPS years and was completed within three months real time. At the time of writing RSA-120 is the largest integer ever factored by a general purpose factoring algorithm. We also present some conservative extrapolations to estimate the difficulty of factoring even larger numbers, using either the quadratic sieve method or the number field sieve, and discuss the issue of the crossover point between these two methods

1994