Details of Method
Let n be the integer we want to factor. We pick an irreducible polynomial f with integer coefficients, and an integer m such that f(m)≡0 (mod n) (we will explain how they are chosen in the next section). Let α be a root of f; we can then form the ring Z. There is a unique ring homomorphism φ from Z to Z/nZ that maps α to m. For simplicity, we'll assume that Z is a unique factorization domain; the algorithm can be modified to work when it isn't, but then there are some additional complications.
Next, we set up two parallel factor bases, one in Z and one in Z. The one in Z consists of all the prime ideals in Z whose norm is bounded by a chosen value . The factor base in Z, as in the rational sieve case, consists of all prime integers up to some other bound.
We then search for relatively prime pairs of integers (a,b) such that:
- a+bm is smooth with respect to the factor base in Z (i.e., it is a product of elements in the factor base).
- a+bα is smooth with respect to the factor base in Z; given how we chose the factor base, this is equivalent to the norm of a+bα being divisible only by primes less than .
These pairs are found through a sieving process, analogous to the Sieve of Eratosthenes; this motivates the name "Number Field Sieve".
For each such pair, we can apply the ring homomorphism φ to the factorization of a+bα, and we can apply the canonical ring homomorphism from Z to Z/nZ to the factorization of a+bm. Setting these equal gives a multiplicative relation among elements of a bigger factor base in Z/nZ, and if we find enough pairs we can proceed to combine the relations and factor n, as described above.
Read more about this topic: Special Number Field Sieve
Famous quotes containing the words details of, details and/or method:
“Patience is a most necessary qualification for business; many a man would rather you heard his story than granted his request. One must seem to hear the unreasonable demands of the petulant, unmoved, and the tedious details of the dull, untired. That is the least price that a man must pay for a high station.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)
“There was a time when the average reader read a novel simply for the moral he could get out of it, and however naïve that may have been, it was a good deal less naïve than some of the limited objectives he has now. Today novels are considered to be entirely concerned with the social or economic or psychological forces that they will by necessity exhibit, or with those details of daily life that are for the good novelist only means to some deeper end.”
—Flannery O’Connor (1925–1964)
“In child rearing it would unquestionably be easier if a child were to do something because we say so. The authoritarian method does expedite things, but it does not produce independent functioning. If a child has not mastered the underlying principles of human interactions and merely conforms out of coercion or conditioning, he has no tools to use, no resources to apply in the next situation that confronts him.”
—Elaine Heffner (20th century)