## 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) :-)