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:
“You that do search for every purling spring
Which from the ribs of old Parnassus flows,
And every flower, not sweet perhaps, which grows
Near thereabouts into your poesy wring;
You that do dictionary’s method bring
Into your rhymes, running in rattling rows;”
—Sir Philip Sidney (1554–1586)
“I have a new method of poetry. All you got to do is look over your notebooks ... or lay down on a couch, and think of anything that comes into your head, especially the miseries.... Then arrange in lines of two, three or four words each, don’t bother about sentences, in sections of two, three or four lines each.”
—Allen Ginsberg (b. 1926)
“... [a] girl one day flared out and told the principal “the only mission opening before a girl in his school was to marry one of those candidates [for the ministry].” He said he didn’t know but it was. And when at last that same girl announced her desire and intention to go to college it was received with about the same incredulity and dismay as if a brass button on one of those candidate’s coats had propounded a new method for squaring the circle or trisecting the arc.”
—Anna Julia Cooper (1859–1964)