Editing General number field sieve (section)

== Method ==
{{Confusing|section|reason=there are no examples or pseudocode|date=May 2021}}
Two [[polynomial]]s ''f''(''x'') and ''g''(''x'') of small [[degree of a polynomial|degrees]] ''d'' and ''e'' are chosen, which have integer coefficients, which are [[irreducible polynomial|irreducible]] over the [[rational number|rationals]], and which, when interpreted [[modular arithmetic|mod ''n'']], have a common integer [[root of a function|root]] ''m''. An optimal strategy for choosing these polynomials is not known; one simple method is to pick a degree ''d'' for a polynomial, consider the expansion of ''n'' in [[radix|base ''m'']] (allowing digits between −''m'' and ''m'') for a number of different ''m'' of order ''n''<sup>1/''d''</sup>, and pick ''f''(''x'') as the polynomial with the smallest coefficients and ''g''(''x'') as ''x''&nbsp;−&nbsp;''m''.

Consider the number field rings '''Z'''[''r''<sub>1</sub>] and '''Z'''[''r''<sub>2</sub>], where ''r''<sub>1</sub> and ''r''<sub>2</sub> are roots of the polynomials ''f'' and ''g''. Since ''f'' is of degree ''d'' with integer coefficients, if ''a'' and ''b'' are integers, then so will be ''b''<sup>''d''</sup>·''f''(''a''/''b''), which we call ''r''. Similarly, ''s'' = ''b''<sup>''e''</sup>·''g''(''a''/''b'') is an integer. The goal is to find integer values of ''a'' and ''b'' that simultaneously make ''r'' and ''s'' [[smooth number|smooth]] relative to the chosen basis of primes. If ''a'' and ''b'' are small, then ''r'' and ''s'' will be small too, about the size of ''m'', and we have a better chance for them to be smooth at the same time.  The current best-known approach for this search is [[lattice sieving]]; to get acceptable yields, it is necessary to use a large factor base.

Having enough such pairs, using [[Gaussian elimination]], one can get products of certain ''r'' and of the corresponding ''s'' to be squares at the same time. A slightly stronger condition is needed—that they are [[field norm|norms]] of squares in our number fields, but that condition can be achieved by this method too.  Each ''r'' is a norm of ''a''&nbsp;−&nbsp;''r''<sub>1</sub>''b'' and hence that the product of the corresponding factors ''a''&nbsp;−&nbsp;''r''<sub>1</sub>''b'' is a square in '''Z'''[''r''<sub>1</sub>], with a "square root" which can be determined (as a product of known factors in '''Z'''[''r''<sub>1</sub>])—it will typically be represented as an irrational [[algebraic number]].  Similarly, the product of the factors ''a''&nbsp;−&nbsp;''r''<sub>2</sub>''b'' is a square in '''Z'''[''r''<sub>2</sub>], with a "square root" which also can be computed.  It should be remarked that the use of Gaussian elimination does not give the optimal run time of the algorithm.  Instead, sparse matrix solving algorithms such as [[Block Lanczos algorithm for nullspace of a matrix over a finite field|Block Lanczos]] or [[Block Wiedemann algorithm|Block Wiedemann]] are used. 

Since ''m'' is a root of both ''f'' and ''g'' mod ''n'', there are [[homomorphism]]s from the rings '''Z'''[''r''<sub>1</sub>] and '''Z'''[''r''<sub>2</sub>] to the ring '''Z'''/''n'''''Z''' (the integers [[Modular arithmetic|modulo ''n'']]), which map ''r''<sub>1</sub> and ''r''<sub>2</sub> to ''m'', and these homomorphisms will map each "square root" (typically not represented as a rational number) into its integer representative. Now the product of the factors ''a''&nbsp;−&nbsp;''mb'' mod ''n'' can be obtained as a square in two ways—one for each homomorphism. Thus, one can find two numbers ''x'' and ''y'', with ''x''<sup>2</sup>&nbsp;−&nbsp;''y''<sup>2</sup> divisible by ''n'' and again with probability at least one half we get a factor of ''n'' by finding the [[greatest common divisor]] of ''n'' and ''x''&nbsp;−&nbsp;''y''.