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:
“There is no method but to be very intelligent.”
—T.S. (Thomas Stearns)
“Methinks the human method of expression by sound of tongue is very elementary, & ought to be substituted for some ingenious invention which should be able to give vent to at least six coherent sentences at once.”
—Virginia Woolf (1882–1941)
“Government by average opinion is merely a circuitous method of going to the devil; those who profess to lead but in fact slavishly follow this average opinion are simply the fastest runners and the loudest squeakers of the herd which is rushing blindly down to its destruction.”
—Thomas Henry Huxley (1825–95)