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.