## Strassen’s Factoring Algorithm

### January 27, 2018

In 1976, Volker Strassen, working with John Pollard, developed a factoring algorithm that is still the fastest proven deterministic factoring algorithm, with time complexity O(*n*^{1/4} log *n*); unfortunately, it is generally slower than other similar algorithms, even Pollard’s rho algorithm. The basic idea is that if you have the product *f _{i}* of a consecutive set of integers modulo the number to be factored

*n*, and that set of integers contains one of the factors of

*n*, then gcd(

*f*,

_{i}*n*) will be greater than 1. Here’s the algorithm:

- Compute
c=n^{1/4}and define an arrayfcontainingcintegers, each initially 1.- In each array element
f, compute the product modulo_{i}nof the integers fromi c+ 1 toc(i+1).- Compute the greatest common divisor of each of the
fwith_{i}n, stopping when you find a (possibly-composite) factor.

The second loop, in Step 3, takes time O(*n*^{1/4} log *n*), so the trick is to compute the products of Step 2 in less time than O(*n*²). That can be done using product trees, as Berstein suggests, but that’s messy and a little bit complicated, and even if you manage to implement it, Strassen’s algorithm still isn’t competitive, so we won’t bother.

Your task is to implement Strassen’s factoring algorithm as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 97

101, 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.