## Strassen’s Factoring Algorithm

We’re going to cheat. The only reason to compute the fi is to take advantage of the fast product trees, and we’re not going to implement that, so instead of pre-computing the fi we compute them one at a time and immediately check the greatest common divisor, returning as soon as we find a factor:

```(define (strassen n)
(call-with-current-continuation
(lambda (return)
(let ((c (iroot 4 n)))
(do ((i 0 (+ i 1))) ((= i c) #f)
(let* ((jmin (+ 1 (* i c))) (jmax (+ jmin c -1)))
(do ((j jmin (+ j 1)) (f 1 (modulo (* f j) n)))
((< jmax j) (let ((g (gcd f n)))
(when (< 1 g) (return g)))))))))))```

As a practical matter, it is probably better to remove small factors with trial division before calling `strassen`, reducing the likelihood of finding a composite factor. Here are some examples:

```> (strassen 1329059)
3119
> (strassen 11111111111111111)
2071723
> (strassen 2071723)
#f```

Strassen’s factoring algorithm has no practical utility. It’s value is that it serves as an upper bound on the complexity of deterministically factoring integers.

You can run the program at https://ideone.com/HPO1aI.

Pages: 1 2