Strassen’s Factoring Algorithm
January 27, 2018
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, as it is slower than other algorithms (Pollard rho, SQUFOF) with the same time complexity. It’s value is that it serves as an proven upper bound on the complexity of deterministically factoring integers.
You can run the program at https://ideone.com/HPO1aI.
Here is a naive implementation in very simple, standard Scheme,
favoring clarity over efficiency.
In Python. I increased the size of the array by 1, as I did not get a factor for n= 97*101 otherwise.
Here’s a solution in C using GMP.
@Paul, my implementation has the same problem you identified. While your modification worked for 97101, it did not work for another problematic case, 5961. With the modification, the input value is returned as the factor.
Output:
My asterisks were used as markup for italics. Let me try again.
@Paul, my implementation has the same problem you identified. While your modification worked for
, it did not work for another problematic case,
. With the modification, the input value is returned as the factor.
A Haskell version.