Editing Dixon's factorization method (section)

==Optimizations==
The [[quadratic sieve]] is an optimization of Dixon's method. It selects values of ''x'' close to the square root of {{var|N}} such that ''x<sup>2</sup>'' modulo ''N'' is small, thereby largely increasing the chance of obtaining a smooth number.

Other ways to optimize Dixon's method include using a better algorithm to solve the matrix equation, taking advantage of the sparsity of the matrix: a number ''z'' cannot have more than <math>\log_2 z</math> factors, so each row of the matrix is almost all zeros.  In practice, the [[Block Lanczos algorithm for nullspace of a matrix over a finite field|block Lanczos algorithm]] is often used. Also, the size of the factor base must be chosen carefully: if it is too small, it will be difficult to find numbers that factorize completely over it, and if it is too large, more relations will have to be collected.

A more sophisticated analysis, using the approximation that a number has all its prime factors less than <math>N^{1/a}</math> with probability about <math>a^{-a}</math> (an approximation to the [[Dickman–de Bruijn function]]), indicates that choosing too small a factor base is much worse than too large, and that the ideal factor base size is some power of <math>\exp\left(\sqrt{\log N \log \log N}\right)</math>.

The optimal complexity of Dixon's method is 
:<math>O\left(\exp\left(2 \sqrt 2 \sqrt{\log n \log \log n}\right)\right)</math>
in [[big-O notation]], or
:<math>L_n [1/2, 2 \sqrt 2]</math>
in [[L-notation]].