Dixon’s Factorization Algorithm

May 13, 2011

In 1981, John D. Dixon, a mathematician at Carleton University, developed the integer factorization algorithm that bears his name. Dixon’s algorithm is not used in practice, because it is quite slow, but it is important in the realm of number theory because it is the only sub-exponential factoring algorithm with a deterministic (not conjectured) run time, and it is the precursor to the quadratic sieve factorization algorithm, which is eminently practical.

Dixon’s algorithm is based on the well-known fact of number theory that, given x2y2 (mod n), with x ≠ ±y (mod n), it is likely that gcd(x-y, n) will be a factor of n. The algorithm is similar to the CFRAC algorithm of Morrison and Brillhart: the first phase finds smooth relations, and the second phase uses linear algebra to combine them and form a factorization. The difference is the first phase, where CFRAC looks in the convergents of the continued fraction of the square root of the number being factored, but Dixon’s algorithm simply chooses numbers at random.

Thus, the first stage of Dixon’s method is this: choose a bound B and identify the factor base of all primes less than B that are quadratic residues of n (their jacobi symbol is 1). Then choose a positive integer r < n, calculate its square modulo n, and if the square is smooth over the factor base, add r and its square to the linear algebra; repeat this step until you have found a sufficient number of smooth squares. The second stage is identical to CFRAC.

Your task is to write a function that factors integers by Dixon’s algorithm. When you are finished you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

One Response to “Dixon’s Factorization Algorithm”

  1. Graham said

    Since a good number of the factorization exercises were posted before I started visiting,
    I think I’ll go through them in chronological order and end up here soon. I’ve just gotten
    through exam week at grad school, so I have a bit of time on my hands (finally) :-)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: