Pollard-Strassen Algorithm

Question

I'm aware that the Pollard-Strassen algorithm can be used to find all prime factors of $n$ not exceeding $B$ in $O\big(n^{\epsilon} B^{1/2}\big)$ time. This is really useful because I need to find all factors less than $n^{1/3}$ to determine if n is squarefree, which could therefore theoretically be done in $O\big(n^{1/6+\epsilon}\big)$.

However I can't find anything more than a brief overview of the algorithm itself, let alone a worked example. Could anyone provide a detailed explanation or example, or reference to where I can find one? Additionally, I'm interested in other algorithms, if they exist, which provide all factors not exceeding $B=\big\lceil n^{1/3} \big\rceil$ quickly.

Answer 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.