Number field sieve factoring

For several years it was believed by some people that a running time of Ln[i, 1] was, in fact, the best achievable by any integer factorization algorithm. This barrier was broken in 1990 with the discovery of the number field sieve. Like the quadratic sieve, the number field sieve is an algorithm in the random square family of methods (§3.2.5). That is, it attempts to find integers x and у such that x2 = у2 (mod n) and x ф ±y (mod n). To achieve this goal, two factor bases are used, one consisting of all prime numbers less than some bound, and the other consisting of all prime ideals of norm less than some bound in the ring of integers of a suitably-chosen algebraic number field. The details of the algorithm are quite complicated, and are beyond the scope of this book.

A special version of the algorithm (the special number field sieve) applies to integers of the form n = re - s for small r and ,s|, and has an expected running time of L„[j, c], where c= (32/9)1/3 и 1.526.

The general version of the algorithm, sometimes called the general number field sieve, applies to all integers and has an expected running time of c], where c = (64/9)1/3 ss

1.923. This is, asymptotically, the fastest algorithm known for integer factorization. The primary reason why the running time of the number field sieve is smaller than that of the quadratic sieve is that the candidate smooth numbers in the former are much smaller than those in the latter.

The general number field sieve was at first believed to be slower than the quadratic sieve for factoring integers having fewer than 150 decimal digits. However, experiments in 1994-1996 have indicated that the general number field sieve is substantially faster than the quadratic sieve even for numbers in the 115 digit range. This implies that the crossover point between the effectiveness of the quadratic sieve vs. the general number field sieve may be 110-120 digits. For this reason, the general number field sieve is considered the current champion of all general-purpose factoring algorithms.

< Prev   CONTENTS   Source   Next >