## The Factorization Of F7: Part 2

### September 17, 2010

We begin with make-row, which returns the exponent vector for a single Qn:

(define (make-row rs fb len)
(let ((vec (make-vector (+ len 1) 0)))
(vector-set! vec 0 (if (odd? (car rs)) 1 0))
(let loop ((i 1) (rs (cdddr rs)) (fb fb))
(cond ((or (null? rs) (null? fb)) vec)
((= (car fb) (car rs))
(vector-set! vec i 1)
(loop (+ i 1) (cdr rs) (cdr fb)))
(else (loop (+ i 1) rs (cdr fb)))))))

Make-ev and make-hv build the exponent and history matrices, respectively:

(define (make-ev fb len residues)
(let loop ((rss residues) (es '()) (as '()) (qs '()))
(values (list->vector (reverse es))
(list->vector (reverse as))
(list->vector (reverse qs)))
(cons (make-row (car rss) fb len) es)

(define (make-hv ev-len)
(let ((hv (make-vector ev-len)))
(do ((i 0 (+ i 1))) ((= i ev-len) hv)
(let ((h (make-vector ev-len 0)))
(vector-set! h i 1)
(vector-set! hv i h)))))

The calculation of the rightmost 1 is shown below. Later, in the answer function, we will keep track of the rightmost 1 in each row rather than recomputing it each time it is needed, just as Morrison and Brillhart did:

(define (right-most-one rv start)
(let loop ((i start))
(cond ((negative? i) i)
((= (vector-ref rv i) 1) i)
(else (loop (- i 1))))))

Finally, we give the code for ANSWER, which initializes the exponent vector and history vector, creates a pointer vector for the rightmost 1 in each column, performs the reduction procedure, and then examines S-sets until it finds one that gives a factorization:

(let-values (((ev av qv) (make-ev fb (length fb) residues)))
(let* ((fb-len (length fb)) (ev-len (vector-length ev))
(hv (make-hv ev-len)) (ptr (make-vector ev-len)))
(do ((i 0 (+ i 1))) ((= i ev-len))
(vector-set! ptr i (right-most-one (vector-ref ev i) fb-len)))
; reduce ev and hv
(do ((j fb-len (- j 1))) ((negative? j))
(let loop ((i 0))
(when (< i ev-len)
(if (= (vector-ref ptr i) j)
(do ((m (+ i 1) (+ m 1))) ((= m ev-len))
(when (= (vector-ref ptr m) j)
(vector-set! ev m (vector-add (vector-ref ev i) (vector-ref ev m)))
(vector-set! hv m (vector-add (vector-ref hv i) (vector-ref hv m)))
(vector-set! ptr m (right-most-one (vector-ref ev m) j))))
(loop (+ i 1))))))
; examine s-sets
(let loop ((i 0))
(cond ((= i ev-len) #f)
((zero? (vector-sum (vector-ref ev i)))
(let ((d (gcd (a-minus-q n (vector-ref hv i) ev-len av qv) n)))
(if (< 1 d n) d (loop (+ i 1)))))
(else (loop (+ i 1))))))))

Answer uses isqrt from the Standard Prelude, plus the utility functions shown below:

(let* ((len (vector-length v1))
(v3 (make-vector len)))
(do ((i 0 (+ i 1))) ((= i len) v3)
(vector-set! v3 i
(if (= (vector-ref v1 i)
(vector-ref v2 i)) 0 1)))))

(define (vector-sum vec)
(do ((i 0 (+ i 1)) (sum 0 (+ sum (vector-ref vec i))))
((= i (vector-length vec)) sum)))

Answer also uses a-minus-q, which takes an S-set and returns a divisor of N; it is up to answer to determine if that factor is useful or trivial; note that the calculation of the square root of q-prod is exact:

(define (a-minus-q n vec ev-len av qv)
(let loop ((i 0) (a-prod 1) (q-prod 1))
(cond ((= i ev-len) (modulo (- a-prod (isqrt q-prod)) n))
((= (vector-ref vec i) 1)
(loop (+ i 1)
(modulo (* a-prod (vector-ref av i)) n)
(* q-prod (vector-ref qv i))))
(else (loop (+ i 1) a-prod q-prod)))))

Using the factor base and residues calculated in the previous exercise, the factorization of F7 is shown below: