Special Number Field Sieve - Limitations of Algorithm

Limitations of Algorithm

This algorithm, as mentioned above, is very efficient for numbers of the form re±s, for r and s relatively small. It is also efficient for any integers which can be represented as a polynomial with small coefficients. This includes integers of the more general form a're±b'sf, and also for many integers whose binary representation has low Hamming weight. The reason for this is as follows: The Number Field Sieve performs sieving in two different fields. The first field is usually the rationals. The second is a higher degree field. The efficiency of the algorithm strongly depends on the norms of certain elements in these fields. When an integer can be represented as a polynomial with small coefficients, the norms that arise are much smaller than those that arise when an integer is represented by a general polynomial. The reason is that a general polynomial will have much larger coefficients, and the norms will be correspondingly larger. The algorithm attempts to factor these norms over a fixed set of prime numbers. When the norms are smaller, these numbers are more likely to factor.