Programming Praxis

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