This results in many rather complicated aspects of the algorithm, as compared to the simpler rational sieve.
The size of the input to the algorithm is log2 n or the number of bits in the binary representation of n. Any element of the order nc for a constant c is exponential in log n. The running time of the number field sieve is super-polynomial but sub-exponential in the size of the input.
This allows us to define the complex product: In general, this leads directly to the algebraic number field
The goal is to find integer values of a and b that simultaneously make r and s smooth relative to the chosen basis of primes.
The current best-known approach for this search is lattice sieving; to get acceptable yields, it is necessary to use a large factor base.
Since m is a root of both f and g mod n, there are homomorphisms from the rings Z[r1] and Z[r2] to the ring Z/nZ (the integers modulo n), which map r1 and r2 to m, and these homomorphisms will map each "square root" (typically not represented as a rational number) into its integer representative.
One such method was suggested by Murphy and Brent;[3] 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[4] were achieved by the method of Thorsten Kleinjung,[5] 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.
[8] Until 2007, the gold-standard implementation was a suite of software developed and distributed by CWI in the Netherlands, which was available only under a relatively restrictive license.
[citation needed] In 2007, Jason Papadopoulos developed a faster implementation of final processing as part of msieve, which is in the public domain.
Both implementations feature the ability to be distributed among several nodes in a cluster with a sufficiently fast interconnect.