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

%d bloggers like this: