<p>Some months ago, before the advent of "CS-Theory", I asked <a href="https://mathoverflow.net/questions/23717/reference-request-given-a-divisor-d-of-n-how-quickly-can-i-obtain-the-largest-f">a question on MathOverflow</a> about efficiently factoring an integer <em>N</em> into coprime factors <em>n</em><sub>1</sub> and <em>n</em><sub>2</sub>, where <em>n</em><sub>1</sub> is a multiple of a given a factor <em>d</em> of <em>N</em>.</p>

<p><a href="https://mathoverflow.net/questions/23717/reference-request-given-a-divisor-d-of-n-how-quickly-can-i-obtain-the-largest-f/23728#23728">One of the answers</a> pointed me to <a href="http://cr.yp.to/coprimes.html" rel="nofollow noreferrer">Dan Bernstein's website</a>, 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 <em>S</em> of integers, a <em>coprime base</em> cb(<em>S</em>) is a set of integers which are coprime to one another, such that each element of <em>S</em> factors (uniquely) as a product of elements of cb(<em>S</em>). Bernstein's site has</p>

<ol>
<li>An article dating from 1998, about constructing a coprime base in "essentially linear time", which is to say time&nbsp; n&nbsp;log&nbsp;(n)<sup>O(1)</sup>&nbsp; (where n is the number of input bits, or equivalently the logarithm of the product of the input set) and;<br><br></li>
<li>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&nbsp; n&nbsp;log&nbsp;(n)<sup>2+o(1)</sup>&nbsp;.</li>
</ol>

<p>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.</p>

<p><strong>Question.</strong> Has there been any more development of the ideas of "<a href="http://cr.yp.to/lineartime/dcba2-20041103.pdf" rel="nofollow noreferrer">Faster factorization into coprimes</a>" &mdash; possibly by different authors &mdash; into a finished article with the run-time as described above? Or is this accepted by the community as essentially complete?</p>

<p>(<em>Edit:</em> 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.)</p>

CC BY-SA 2.5
2010-11-29T15:31:45.760Z
[Just a suggestion] You can contact the author (Bernstein) and ask him, as well.
Sadeq Dousti
CC BY-SA 2.5
2010-11-29T15:48:03.777Z
@Sadeq: that would be the obvious, direct approach, now wouldn't it? Let me give that a try.
Niel de Beaudrap
CC BY-SA 2.5
2010-11-30T16:30:16.827Z
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.
Niel de Beaudrap
<ds.algorithms><factoring><nt.number-theory>
Reference request: a more complete "faster factorization into coprimes"
Niel de Beaudrap
# Reference request: a more complete "faster factorization into coprimes"

(Asked by: username_0 on 2010-11-29)

Some months ago, before the advent of "CS-Theory", I asked [a question on MathOverflow](https://mathoverflow.net/questions/23717/reference-request-given-a-divisor-d-of-n-how-quickly-can-i-obtain-the-largest-f) about efficiently factoring an integer *N* into coprime factors *n*1 and *n*2, where *n*1 is a multiple of a given a factor *d* of *N*.

[One of the answers](https://mathoverflow.net/questions/23717/reference-request-given-a-divisor-d-of-n-how-quickly-can-i-obtain-the-largest-f/23728#23728) pointed me to [Dan Bernstein's website](http://cr.yp.to/coprimes.html), 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](http://cr.yp.to/lineartime/dcba2-20041103.pdf)" — 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.)

**Tags:** ds.algorithms, factoring, nt.number-theory

> **Comments:**
> **username_1**: [Just a suggestion] You can contact the author (Bernstein) and ask him, as well.  
> **username_0**: @Sadeq: that would be the obvious, direct approach, now wouldn't it? Let me give that a try.  
> **username_0**: 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.  

---

## 0 answers

