Бүтін санды жіктеу алгоритмі: Төрткіш елек (Quadratic Sieve)

Integer factorization algorithm
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.

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 data collection phase can be easily parallelized to many processors, but the data processing phase requires large amounts of memory, and is difficult to parallelize efficiently over many nodes or if the processing nodes do not each have enough memory to store the whole matrix. The block Wiedemann algorithm can be used in the case of a few systems each capable of holding the matrix. The naive approach to finding a congruence of squares is to pick a random number, square it, divide by n and hope the least non negative remainder is a perfect square. For example, This approach finds a congruence of squares only rarely for large n, but when it does find one, more often than not, the congruence is nontrivial and the factorization is complete. This is roughly the basis of Fermat's factorization method. The quadratic sieve is a modification of Dixon's factorization method. The general running time required for the quadratic sieve (to factor an integer n) is

in the L notation. The constant e is the base of the natural logarithm.

The quadratic sieve attempts to find pairs of integers x and y(x) (where y(x) is a function of x) satisfying a much weaker condition than x2 ≡ y2 (mod n). It selects a set of primes called the factor base, and attempts to find x such that the least absolute remainder of y(x) = x2 mod n factorizes completely over the factor base. Such y values are said to be smooth with respect to the factor base. The factorization of a value of y(x) that splits over the factor base, together with the value of x, is known as a relation. The quadratic sieve speeds up the process of finding relations by taking x close to the square root of n. This ensures that y(x) will be smaller, and thus have a greater chance of being smooth. This implies that y is on the order of 2x[]. However, it also implies that y grows linearly with x times the square root of n.

Another way to increase the chance of smoothness is by simply increasing the size of the factor base. However, it is necessary to find at least one smooth relation more than the number of primes in the factor base, to ensure the existence of a linear dependency.

There are several ways to check for smoothness of the ys. The most obvious is by trial division, although this increases the running time for the data collection phase. Another method that has some acceptance is the elliptic curve method (ECM). In practice, a process called sieving is typically used. If f(x) is the polynomial we have

Thus solving f(x) ≡ 0 (mod p) for x generates a whole sequence of numbers y for which y=f(x), all of which are divisible by p. This is finding a square root modulo a prime, for which there exist efficient algorithms, such as the Shanks–Tonelli algorithm. (This is where the quadratic sieve gets its name: y is a quadratic polynomial in x, and the sieving process works like the Sieve of Eratosthenes.) The sieve starts by setting every entry in a large array A[] of bytes to zero. For each p, solve the quadratic equation mod p to get two roots α and β, and then add an approximation to log(p) to every entry for which y(x) = 0 mod p that is, A[kp + α] and A[kp + β]. It is also necessary to solve the quadratic equation modulo small powers of p in order to recognise numbers divisible by small powers of a factor base prime. At the end of the factor base, any A[] containing a value above a threshold of roughly log(x2−n) will correspond to a value of y(x) which splits over the factor base. The information about exactly which primes divide y(x) has been lost, but it has only small factors, and there are many good algorithms for factoring a number known to have only small factors, such as trial division by small primes, SQUFOF, Pollard rho, and ECM, which are usually used in some combination. There are many y(x) values that work, so the factorization process at the end doesn't have to be entirely reliable; often the processes misbehave on say 5% of inputs, requiring a small amount of extra sieving.

This example will demonstrate standard quadratic sieve without logarithm optimizations or prime powers. Let the number to be factored N = 15347, therefore the ceiling of the square root of N is 124. Since N is small, the basic polynomial is enough: y(x) = (x + 124)2 − 15347.

In practice, many different polynomials are used for y, since only one polynomial will not typically provide enough (x, y) pairs that are smooth over the factor base. The polynomials used must have a special form, since they need to be squares modulo n. The polynomials must all have a similar form to the original y(x) = x2 − n:

Assuming is a multiple of A, so that the polynomial y(x) can be written as If A is a square, then only the factor has to be considered. This approach (called MPQS, Multiple Polynomial Quadratic Sieve) is ideally suited for parallelization, since each processor involved in the factorization can be given n, the factor base and a collection of polynomials, and it will have no need to communicate with the central processor until it is finished with its polynomials.

If, after dividing by all the factors less than A, the remaining part of the number (the cofactor) is less than A2, then this cofactor must be prime. In effect, it can be added to the factor base, by sorting the list of relations into order by cofactor. If y(a) = 7*11*23*137 and y(b) = 3*5*7*137, then y(a)y(b) = 3*5*11*23 * 72 * 1372. This works by reducing the threshold of entries in the sieving array above which a full factorization is performed.

Reducing the threshold even further, and using an effective process for factoring y(x) values into products of even relatively large primes ECM is superb for this can find relations with most of their factors in the factor base, but with two or even three larger primes. Cycle finding then allows combining a set of relations sharing several primes into a single relation.

Until the discovery of the number field sieve (NFS), QS was the asymptotically fastest known general purpose factoring algorithm. Now, Lenstra elliptic curve factorization has the same asymptotic running time as QS (in the case where n has exactly two prime factors of equal size), but in practice, QS is faster since it uses single precision operations instead of the multi precision operations used by the elliptic curve method. On April 2, 1994, the factorization of RSA 129 was completed using QS. It was a 129 digit number, the product of two large primes, one of 64 digits and the other of 65 digits. The factor base for this factorization contained 524339 primes. The data collection phase took 5000 MIPS years, done in distributed fashion over the Internet. The data collected totaled 2GB. The data processing phase took 45 hours on Bellcore's (now Telcordia Technologies) MasPar (massively parallel) supercomputer. This was the largest published factorization by a general purpose algorithm, until NFS was used to factor RSA 130, completed April 10, 1996. All RSA numbers factored since then have been factored using NFS. The current QS factorization record is the 140 digit (463 bit) RSA 140, which was factored by Patrick Konsor in June 2020 using approximately 6,000 core hours over 6 days.