Editing General number field sieve (section)

== 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 {{mvar|n}} in base {{mvar|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;<ref>{{citation |first1=B. |last1=Murphy |first2=R. P. |last2=Brent |title=On quadratic polynomials for the number field sieve |journal=Australian Computer Science Communications |volume=20 |date=1998 |pages=199–213 |url=http://maths-people.anu.edu.au/~brent/pub/pub178.html }}</ref> 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<ref>{{citation | last=Franke |first=Jens |year=2006 |title=On RSA 200 and larger projects |url=http://www.hyperelliptic.org/tanja/SHARCS/talks06/Jens_Franke.pdf }}</ref> were achieved by the method of [[Thorsten Kleinjung]],<ref>{{cite journal | last=Kleinjung |first=Thorsten |date=October 2006 |title=On polynomial selection for the general number field sieve |journal=Mathematics of Computation |volume=75 |pages=2037–2047 |url=https://www.ams.org/mcom/2006-75-256/S0025-5718-06-01870-9/S0025-5718-06-01870-9.pdf |access-date=2007-12-13 |doi=10.1090/S0025-5718-06-01870-9 |issue=256|bibcode=2006MaCom..75.2037K |doi-access=free }}</ref> which allows {{math|''g''(''x'') {{=}} ''ax''&nbsp;+&nbsp;''b''}}, and searches over {{mvar|a}} composed of small prime factors congruent to 1 modulo 2{{math|''d''}} and over leading coefficients of {{mvar|f}} which are divisible by 60.