Basic Idea
Dixon's method is based on finding a congruence of squares modulo the integer N which we intend to factor. Fermat's factorization algorithm finds such a congruence by selecting random or pseudo-random x values and hoping that the integer x2 mod N is a perfect square (in the integers):
For example, if N = 84923, we notice (by starting at 292, the first number greater than √N and counting up) that 5052 mod 84923 is 256, the square of 16. So (505 − 16)(505 + 16) = 0 mod 84923. Computing the greatest common divisor of 505 − 16 and N using Euclid's algorithm gives us 163, which is a factor of N.
In practice, selecting random x values will take an impractically long time to find a congruence of squares, since there are only √N squares less than N.
Dixon's method replaces the condition "is the square of an integer" with the much weaker one "has only small prime factors"; for example, there are 292 squares smaller than 84923; 662 numbers smaller than 84923 whose prime factors are only 2,3,5 or 7; and 4767 whose prime factors are all less than 30. (Such numbers are called B-smooth with respect to some bound B.)
If we have lots of numbers whose squares can be factorized as for a fixed set of small primes, linear algebra modulo 2 on the matrix will give us a subset of the whose squares combine to a product of small primes to an even power — that is, a subset of the whose squares multiply to the square of a (hopefully different) number mod N.
Read more about this topic: Dixon's Factorization Method
Famous quotes containing the words basic and/or idea:
“Surrealism is not a school of poetry but a movement of liberation.... A way of rediscovering the language of innocence, a renewal of the primordial pact, poetry is the basic text, the foundation of the human order. Surrealism is revolutionary because it is a return to the beginning of all beginnings.”
—Octavio Paz (b. 1914)
“The whole idea of image is so confused. On the one hand, Madison Avenue is worried about the image of the players in a tennis tour. On the other hand, sports events are often sponsored by the makers of junk food, beer, and cigarettes. What’s the message when an athlete who works at keeping her body fit is sponsored by a sugar-filled snack that does more harm than good?”
—Martina Navratilova (b. 1956)