Some months ago, before the advent of "CS-Theory", I asked a question on MathOverflow about efficiently factoring an integer N into coprime factors n1 and n2, where n1 is a multiple of a given a factor d of N.
One of the answers pointed me to Dan Bernstein's website, which has notes on obtaining a coprime base for a set of integers (and algorithms which work in more general settings than integers). For a set S of integers, a coprime base cb(S) is a set of integers which are coprime to one another, such that each element of S factors (uniquely) as a product of elements of cb(S). Bernstein's site has
- An article dating from 1998, about constructing a coprime base in "essentially linear time", which is to say time n log (n)O(1) (where n is the number of input bits, or equivalently the logarithm of the product of the input set) and;
- A draft manuscript from 2004 (which announces its own preliminariness), on "faster factorization into coprimes", which gives a sketch of how to compute a coprime base in time n log (n)2+o(1) .
After a search for a "more complete" version of the second, or follow-up work by others, I was unable to find much more than links to one or the other of these articles, and slide-show presentations which again point to these articles.
Question. Has there been any more development of the ideas of "Faster factorization into coprimes" — possibly by different authors — into a finished article with the run-time as described above? Or is this accepted by the community as essentially complete?
(Edit: as I've now noted in the comments, Dan Bernstein himself says that he has not yet finished his results. But I'm still interested in finished results by others with comparable run-times, possibly for special cases, but only over the integers.)
