# Pollard-Strassen Algorithm

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.

-
I was going to write it myself, but a quick google search lead me to this. Unless the algorithm you wanted is not this.. – Karolis Juodelė Aug 22 '12 at 19:03
Actually those are both Pollard's rho algorithm. It's a probabilistic algorithm and also only works at finding factors of any size, not less than a specific bound. – LordLing Aug 22 '12 at 21:49
I should add: you can see how it's difficult for me to track down this algorithm's details though! :) There are only a few mentions of it. – LordLing Aug 22 '12 at 21:51

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.

-
Should that 0.25 be 0.34? – 6c1 Nov 13 '12 at 14:07