Pollard-Strassen Algorithm

Solution 1:

The basic idea of Strassen's factorization method 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 the factors of $n$, then $\mathrm{gcd}(f_i, n)$ will be greater than unity. The trick then is to compute $f_i$ for non-overlapping sets of possible factors quickly.

Here is a brute-force example that shows how the 9th block of numbers reveals 293 as a factor of 1000009:

var n = (BigInteger)1000009;
var c = (int)Math.Floor(Math.Pow((double)n, 0.25));
var f = new BigInteger[c];
for (var i = 0; i < c; i++)
{
    f[i] = 1;
    var jmin = 1 + i * c;
    var jmax = jmin + c - 1;
    for (var j = jmin; j <= jmax; j++)
        f[i] = f[i] * j % n;
}
for (var i = 0; i < c; i++)
{
    var factor = BigInteger.GreatestCommonDivisor(f[i], n);
    if (factor != 1)
    {
        Console.WriteLine("i = {0}, factor = {1}", i, factor);
        break;
    }
}

The second for-loop takes $O(n^{1/4}\log n)$, and so the hard work of the algorithm is to compute $f_i$ in faster than the $O(n^{1/2})$ demonstrated in the first for-loop above. How this is done is by using subproduct trees and multipoint evaluation. Here is a slide presentation that describes the details pretty well. Also this paper (search for "Main algorithmic ideas") has a good high level overview of the algorithm. Finally, subproduct trees are given a good treatment in this presentation, Asymptotically fast algorithms for modern computer algebra.