Usage
The factor base is a relatively small set of prime numbers P. Say we want to factorize an integer n. We generate, in some way, a large number of congruent integer pairs (x, y) for which and, and x, y can be completely factorized over the chosen factor base—that is, they are p-smooth for the largest prime p in P.
We find a subset S of the integer pairs such that and are both perfect squares. Over our factor base this reduces to adding exponents of their prime factors, modulo 2, as we can distinguish squares from non-squares simply by checking the parity of the exponents.
We can represent each x and y as a vector of a matrix with 0 and 1 entries for the parity of each exponent. This essentially reformulates the problem into a system of linear equations, which can be solved using numerous methods such as Gaussian elimination; in practice advanced methods like the block Lanczos algorithm are used, that take advantage of certain properties of the system.
Once such a subset is found, we have essentially found a congruence of squares modulo n and can attempt to factorize n. This congruence may generate the trivial ; in this case we try to find another suitable subset. If no such subset is found, we can search for more (x, y) pairs, or try again using a different factor base.
Read more about this topic: Factor Base
Famous quotes containing the word usage:
“Pythagoras, Locke, Socrates—but pages
Might be filled up, as vainly as before,
With the sad usage of all sorts of sages,
Who in his life-time, each was deemed a bore!
The loftiest minds outrun their tardy ages.”
—George Gordon Noel Byron (1788–1824)
“...Often the accurate answer to a usage question begins, “It depends.” And what it depends on most often is where you are, who you are, who your listeners or readers are, and what your purpose in speaking or writing is.”
—Kenneth G. Wilson (b. 1923)
“Girls who put out are tramps. Girls who don’t are ladies. This is, however, a rather archaic usage of the word. Should one of you boys happen upon a girl who doesn’t put out, do not jump to the conclusion that you have found a lady. What you have probably found is a lesbian.”
—Fran Lebowitz (b. 1951)