General Number Field Sieve - Improving Polynomial Choice

Improving Polynomial Choice

The choice of polynomial can dramatically affect the time to complete the remainder of the algorithm. The method of choosing polynomials based on the expansion of n in base m shown above is suboptimal in many practical situations, leading to the development of better methods.

One such method was suggested by Murphy and Brent; they introduce a two-part score for polynomials, based on the presence of roots modulo small primes and on the average value that the polynomial takes over the sieving area.

The best reported results were achieved by the method of Thorsten Kleinjung, which allows g(x) = ax + b, and searches over a composed of small prime factors congruent to 1 modulo 2d and over leading coefficients of f which are divisible by 60.

Read more about this topic:  General Number Field Sieve

Famous quotes containing the words improving and/or choice:

    I know of no pursuit in which more real and important services can be rendered to any country than by improving its agriculture, its breed of useful animals, and other branches of a husbandman’s cares.
    George Washington (1732–1799)

    I am a good horse to travel, but not from choice a roadster. The landscape-painter uses the figures of men to mark a road. He would not make that use of my figure.
    Henry David Thoreau (1817–1862)