Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Should that 0.25 be 0.34? –  6c1 Nov 13 '12 at 14:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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