Daniel Shanks’ Square Form Factorization Algorithm

August 24, 2010

In the mid-1970s, Daniel Shanks exploited the binary quadratic forms introduced by Legendre in the late eighteenth century and perfected by Gauss in the early nineteenth century to create a method of factoring integers. Binary quadratic forms are expressions of the form Ax2 + Bxy + Cy2 with A, B and C integers, normally represented as the triple (A, B, C). Binary quadratic forms are often called square forms.

We won’t discuss the mathematics of square forms, but we do need to know how to reduce a square form. A discriminant delta is calculated as Δ = b2 − 4ac. A single reduction step is called a rho reduction, and is given by ρ(a, b, c) = (c, r, (r2−Δ)/4c) where r is that unique integer b mod 2c such that −|c| < r <= |c|, if √Δ < |c|, or √Δ − 2|c| < r < √Δ, if |c| < √Δ.

A square form is in reduced form if |√Δ−2|a|| < b < √Δ; this reduction is accomplished by continually applying ρ until the reduced form is achieved.

Shanks’ method uses two loops. First, an initial square form is calculated, based on the number to be factored, which must be odd, composite, and not a perfect square; the details of that initialization are tedious, and appear in the solution on the next page. Then the square form is repeatedly reduced (this is the “forward” loop) until it is in proper form, which is described below. Then the reduced inverse square root of the square form calculated in the forward loop is reduced in a “backward” loop until a factor is identified when two successive square forms (A, B, C=c2) have the same B; the factor is then c, if c is odd, or c/2, if c is even. The reduced inverse square root of (A, B, C=c2) is initially (−c, B, −cA), which is then put into reduced form as described above.

Shanks defined a square form as proper using a queue of values derived in a rather complicated way. We will use a simpler method known as a sufficient list. Let L be the integer square root of the square root of the discriminant. If a square form (A, B, C) is encountered with |C| < L with C even, or |C| < L/2 with C odd, then C is placed on the sufficient list. Then a square form (A, B, C=c2) is proper if c is not on the sufficient list.

Your task is to write a function to factor integers using Shanks’ square form algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

2 Responses to “Daniel Shanks’ Square Form Factorization Algorithm”

  1. programmingpraxis said

    Here is a version of squfof that builds in the calculations for the multiplier, given as k:

    (define (squfof n k)
      ; assumes n is odd, composite, and not a perfect square
      (define (enqueue f m q l)
        (let* ((x (abs (caddr f))) (g (quotient x (gcd x m))))
          (if (and (<= g l) (not (member g q))) (cons g q) q)))
      (define (inv-sqrt f c)
        (list (- c) (cadr f) (* -1 c (car f))))
      (let* ((kn (* k n)) (n4 (= (modulo n 4) 1)) (m (if n4 k (* 2 k)))
             (d (if n4 kn (* 4 k n))) (s (isqrt d))
             (b (if n4 (+ (* 2 (quotient (- s 1) 2)) 1) (* 2 (quotient s 2))))
             (delta (quotient (- (* b b) d) 4))
             (f (list 1 b delta)) (l (isqrt s)) (bound (* 4 l)))
       (let loop ((i 2) (f (rho f)) (q (enqueue f m '() l)))
          (cond ((or (< bound i) (= (caddr f) 1)) #f)
                ((square? (caddr f)) => (lambda (c)
                  (if (member c q)
                      (loop (+ i 1) (rho f) (enqueue f m q l))
                      (let pool ((g (reduce (inv-sqrt f c))))
                        (let ((new-g (rho g)))
                          (if (= (cadr g) (cadr new-g))
                              (let* ((c (abs (caddr g)))

  2. […] factoring algorithms. We studied the “binary quadratic forms” variant of SQUFOF in a previous exercise; today we study the “continued fraction” variant of […]

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


Get every new post delivered to your Inbox.

Join 645 other followers

%d bloggers like this: