Method
Suppose we are trying to factor the composite number N. We choose a bound B, and identify the factor base (which we will call P), the set of all primes less than or equal to B. Next, we search for positive integers z such that z2 mod N is B-smooth. We can therefore write, for suitable exponents ak,
When we have generated enough of these relations (it's generally sufficient that the number of relations be a few more than the size of P), we can use the methods of linear algebra (for example, Gaussian elimination) to multiply together these various relations in such a way that the exponents of the primes on the right-hand side are all even:
This gives us a congruence of squares of the form a2 ≡ b2 (mod N), which can be turned into a factorization of N, N = gcd(a + b, N) × (N/gcd(a + b, N)). This factorization might turn out to be trivial (i.e. N = N × 1), which can only happen if a ≡ ±b (mod N), in which case we have to try again with a different combination of relations; but with luck we will get a nontrivial pair of factors of N, and the algorithm will terminate.
Read more about this topic: Dixon's Factorization Method
Famous quotes containing the word method:
““English! they are barbarians; they don’t believe in the great God.” I told him, “Excuse me, Sir. We do believe in God, and in Jesus Christ too.” “Um,” says he, “and in the Pope?” “No.” “And why?” This was a puzzling question in these circumstances.... I thought I would try a method of my own, and very gravely replied, “Because we are too far off.” A very new argument against the universal infallibility of the Pope.”
—James Boswell (1740–1795)
“Unlike Descartes, we own and use our beliefs of the moment, even in the midst of philosophizing, until by what is vaguely called scientific method we change them here and there for the better. Within our own total evolving doctrine, we can judge truth as earnestly and absolutely as can be, subject to correction, but that goes without saying.”
—Willard Van Orman Quine (b. 1908)
“The method of painting is the natural growth out of a need. I want to express my feelings rather than illustrate them. Technique is just a means of arriving at a statement.... I can control the flow of paint: there is no accident, just as there is no beginning and no end.”
—Jackson Pollock (1912–1956)