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.

About these ads

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 [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: