Dixon’s Factorization Algorithm

May 13, 2011

We will steal most of the code from CFRAC; you will probably want to re-read the two previous CFRAC exercises before you read this solution. The only change we make is to write a new residue procedure:

(define (residue n k fb lim)
  (let loop ((r (isqrt n)) (qs '()))
    (if (zero? lim) (reverse qs)
      (let* ((r2n (modulo (* r r) n))
             (fs (smooth n r2n fb)))
        (cond ((null? fs)
                (let ((d (gcd (- r (isqrt r2n)) n)))
                  (if (< 1 d n) d (loop (+ r 1) qs))))
              (fs (loop (+ r 1) (cons (cons* 0 r2n r fs) qs)))
              (else (loop (+ r 1) qs)))))))

Dixon’s algorithm chooses r at random, but we instead choose r systematically, starting with √n and increasing by 1 at each step. Residue takes a k parameter, for compatibility with the rest of the program, but doesn’t use it. Everything else is the same as CFRAC.

Dixon’s algorithm is quite slow. The example computes the factorization of the 73rd Fibonacci number, 806515533049393 = 9375829 × 86020717 in about an hour; for comparison, Pollard’s rho algorithm computes the factorization in a few milliseconds. But the value of Dixon’s algorithm is not that it is practical for factoring integers but that the randomization allows it to be analyzed and its “big-oh” run-time determined, which can’t be done for any of the other advanced factorization algorithms such as elliptic curves or quadratic sieve.

The code is assembled at http://programmingpraxis.codepad.org/NVi2RHLa.


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 )

Connecting to %s

%d bloggers like this: