## 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 *Q _{n}* 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 F_{7}, 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 *Q _{n}* 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 *Q _{n}* 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 F_{7}:

`> (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 *Q _{n}*; for some unexplained reason, we found 4034. The maximum number of factors for any of the 4034

*Q*is 12, and a total of 29326 factors, about 7.3 per

_{n}*Q*, were found.

_{n}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.

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