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

  1. 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;

  2. 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.)

  • 1
    $\begingroup$ [Just a suggestion] You can contact the author (Bernstein) and ask him, as well. $\endgroup$ Nov 29, 2010 at 15:31
  • 1
    $\begingroup$ @Sadeq: that would be the obvious, direct approach, now wouldn't it? Let me give that a try. $\endgroup$ Nov 29, 2010 at 15:48
  • 3
    $\begingroup$ Dan responded today, saying that he hasn't taken the time to finish the writeup yet. So it would seem that in the general case, there is not yet a complete version available by the original author. $\endgroup$ Nov 30, 2010 at 16:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.