14
$\begingroup$

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.

  • 0
    [This arXiv paper](https://arxiv.org/pdf/1408.2608.pdf) appeared 4 years after your question. You may be interested in it and its references.2018-07-09

1 Answers 1

12

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.

  • 0
    Should that 0.25 be 0.34?2012-11-13