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.

  • $\begingroup$ I was going to write it myself, but a quick google search lead me to this. Unless the algorithm you wanted is not this.. $\endgroup$ – Karolis Juodelė Aug 22 '12 at 19:03
  • $\begingroup$ 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. $\endgroup$ – LordLing Aug 22 '12 at 21:49
  • $\begingroup$ 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. $\endgroup$ – LordLing Aug 22 '12 at 21:51
  • $\begingroup$ The method is also described in the book Prime Numbers by Crandall and Pomerance (2005), in the chapter 5.5 Polynomial evaluation method. $\endgroup$ – minmax Jul 6 '18 at 21:12
  • $\begingroup$ This arXiv paper appeared 4 years after your question. You may be interested in it and its references. $\endgroup$ – user21820 Jul 9 '18 at 2:14

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);

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.

  • $\begingroup$ Should that 0.25 be 0.34? $\endgroup$ – 6c1 Nov 13 '12 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.