## The Factorization Of F7: Part 1

### September 14, 2010

`Make-factor-base` returns a list of primes included in the factor base. The arguments include both bound, the largest possible prime to be included in the list, and lim, the number of factors to be included in the list, since different uses may require different arguments:

```(define (make-factor-base n k bound lim)   (let loop ((i (- lim 1)) (ps (cdr (primes bound))) (fb '(2)))     (cond ((or (zero? i) (null? ps)) (reverse fb))           ((not (negative? (jacobi (* k n) (car ps))))             (loop (- i 1) (cdr ps) (cons (car ps) fb)))           (else (loop i (cdr ps) fb)))))```

`Smooth` determines if Qn factors over the factor base, using trial division, except that even-power factors are excluded by the `if` in the second `cond` clause. If a factorization is found, the list of factors is returned, otherwise `#f`:

```(define (smooth n q fb)   (let loop ((q q) (fb fb) (fs '()) (i 0))     (cond ((= q 1) (reverse fs))           ((null? fb) #f)           ((zero? (modulo q (car fb)))             (if (and (pair? fs) (= (car fb) (car fs)))                 (loop (/ q (car fb)) fb (cdr fs) (+ i 1))                 (loop (/ q (car fb)) fb (cons (car fb) fs) (+ i 1))))           (else (loop q (cdr fb) fs (+ i 1))))))```

In their article, Morrison and Brillhart give a “large-prime” variant of the Q-factoring procedure, but specifically state that they did not use it in their factorization of F7, so neither will we.

`Residue` implements the RESIDUE program of Morrison and Brillhart. We made two changes for clarity, renaming n as `i` and q as `t`, since Scheme doesn’t distinguish case. Otherwise, we follow the algorithm of Morrison and Brillhart exactly; note the first clause of the `cond`, which performs an early return if it finds a Qn that is a perfect square:

```(define (residue n k fb lim)   (let* ((kn (* k n)) (g (isqrt kn)) (a-3 0) (a-2 1)          (q-2 kn) (r-2 g) (g+p-1 g) (q-1 1)          (t-1 (quotient g+p-1 q-1)) (r-1 (- g+p-1 (* q-1 t-1)))          (q0 (+ q-2 (* t-1 (- r-1 r-2)))))     (let loop ((a-2 1) (a-1 g) (q-1 1) (r-1 0) (g+p (+ g g)) (q q0) (i 1) (qs '()) (lim lim))       ; (for-each display `(,i " " ,g+p " " ,q " " ,a-1 #\newline))       (if (or (= q 1) (zero? lim)) (reverse qs)         (let* ((t (quotient g+p q))                (r (- g+p (* q t)))                (a (modulo (+ (* t a-1) a-2) n))                (q+1 (+ q-1 (* t (- r r-1))))                (fs (smooth n q fb)))           (cond ((null? fs)                   (let ((d (gcd (- a-1 (isqrt q)) n)))                     (if (< 1 d n) d                       (loop a-1 a q r (- (* 2 g) r) q+1 (+ i 1) qs (- lim 1)))))                 (fs (loop a-1 a q r (- (* 2 g) r) q+1 (+ i 1) (cons (cons* i q a-1 fs) qs) (- lim 1)))                 (else (loop a-1 a q r (- (* 2 g) r) q+1 (+ i 1) qs (- lim 1)))))))))```

Here are two examples, the second showing a short-circuit factor when a perfect square Qn is found:

```> (residue 13290059 1 '(2 5 31 41 43 53 113) 44) ((5 2050 171341 2 41)  (10 1333 6700527 31 43)  (22 4633 5235158 41 113)  (23 226 1914221 2 113)  (26 3286 11455708 2 31 53)  (31 5650 1895246 2 113)  (40 4558 3213960 2 43 53)) > (residue 13290059 1 '(2 5 31 41 43 53 113) 60) 4261```

It takes several minutes to make the corresponding calculations for F7:

```> (define f7 (+ (expt 2 (expt 2 7) 1)) > (define fb (make-factor-base f7 257 60000 2700)) > (define residues (residue f7 257 fb 1330000))```

The largest of the 2700 primes in the factor base is 52183. Morrison and Brillhart found 2059 factored Qn; for some unexplained reason, we found 4034. The maximum number of factors for any of the 4034 Qn is 12, and a total of 29326 factors, about 7.3 per Qn, were found.

We used `cons*` and `isqrt` from the Standard Prelude, `primes` from the exercise on the Sieve of Eratosthenes and `jacobi` from the exercise on modular arithmetic. You can run the program at http://programmingpraxis.codepad.org/xbOhfe1M.

Pages: 1 2

### One Response to “The Factorization Of F7: Part 1”

1. […] (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 […]