## 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 *Ax*^{2} + *Bxy* + *Cy*^{2} 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 Δ = *b*^{2} − 4*ac*. A single reduction step is called a rho reduction, and is given by ρ(*a*, *b*, *c*) = (*c*, *r*, (*r*^{2}−Δ)/4*c*) where *r* is that unique integer *b* mod 2*c* 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*=*c*^{2}) 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*=*c*^{2}) 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*=*c*^{2}) 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.

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)))

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