Editing Quadratic sieve (section)

==Basic aim==
The algorithm attempts to set up a [[congruence of squares]] [[modular arithmetic|modulo]] ''n'' (the integer to be factorized), which often leads to a factorization of ''n''. The algorithm works in two phases: the ''data collection'' phase, where it collects information that may lead to a congruence of squares; and the ''data processing'' phase, where it puts all the data it has collected into a [[Matrix (mathematics)|matrix]] and solves it to obtain a congruence of squares. The data collection phase can be easily [[parallel computing|parallelized]] to many processors, but the data processing phase requires large amounts of memory, and is difficult to parallelize efficiently over many nodes or if the processing nodes do not each have enough memory to store the whole matrix. The [[block Wiedemann algorithm]] can be used in the case of a few systems each capable of holding the matrix.

The naive approach to finding a congruence of squares is to pick a random number, square it, divide by ''n'' and hope the least non-negative remainder is a [[Square number|perfect square]]. For example, <math>80^2 \equiv 441 = 21^2 \pmod{5959}</math>. This approach finds a congruence of squares only rarely for large ''n'', but when it does find one, more often than not, the congruence is nontrivial and the factorization is complete. This is roughly the basis of [[Fermat's factorization method]].

The quadratic sieve is a modification of [[Dixon's factorization method]]. The general running time required for the quadratic sieve (to factor an integer ''n'') is conjectured to be
:<math>e^{(1 + o(1))\sqrt{\ln n \ln\ln n}} =L_n\left[1/2,1\right]</math>
in the  [[L-notation]].<ref>{{Cite news|last=Pomerance|first=Carl|author-link=Carl Pomerance|date=December 1996|title=A Tale of Two Sieves|periodical=[[Notices of the AMS]]|volume=43|issue=12|pages=1473–1485|url=https://www.ams.org/notices/199612/pomerance.pdf}}</ref> The constant ''e'' is the base of the natural logarithm.