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(n1/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 fi 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(fi, n) will be greater than 1. Here’s the algorithm:
- Compute c = n1/4 and define an array f containing c integers, each initially 1.
- In each array element fi, compute the product modulo n of the integers from i c + 1 to c(i+1).
- Compute the greatest common divisor of each of the fi with n, stopping when you find a (possibly-composite) factor.
The second loop, in Step 3, takes time O(n1/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.
Programming Praxis 