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.
