This is quite likely to be a solved problem, perhaps even a standard exercise. However, being a non-[number theorist], I don't know where to look. A quick perusal of the basic starting references of Google, CLRS, and Bach+Shallit does not seem to help.


*Problem.* I have an integer *N*, and a divisor *d*. What is a good upper bound on the time required to compute coprime integers *n*1 and *n*2 , such that *N* = *n*1*n*2 , and such that *d* divides *n*1?


**Actual Question.** What is a good reference for the solution / time requirements for this problem?


*Solution to problem.* As I'm aware that this may also be an exercise in some number-theory class, I'll outline a very reasonable iterative approach as a good-faith gesture.


Define sequences *xj* , *yj* , and *gj* by the recurrences 


$\begin{align}
\quad x\_1 =& d & \quad && x\_{j+1} =& x\_j g\_j \\\\
y\_1 =& N/d &&& y\_{j+1} =& y\_j / g\_j \\\\
g\_1 =& \gcd(x\_1, y\_1) &&& g\_{j+1} =& \gcd(x\_j, y\_j) 
\end{align}$


which eventually converge. When this occurs (i.e. for *j* sufficiently large that *gj* = 1), we may let *n*1 = *xj* and *n*2 = *yj* .


Note that for any *j* such that *xj* ≥ *yj* , we may show without too much difficulty that *g**j*+1 = 1; so the last few iterations take time O( log(*N*)2 ), and the time required for the preceding iterations increases monotonically with *xj* . Considering the prime-power decompositions of *xj* and of *N*, we may note that the exponent of the maximal power of each prime *p* dividing *xj* doubles with each succesive iteration, until it saturates the exponent of the maximal power of *p* which divides *N*. Thus, the number of iterations required will be bounded above by something like log log(*N*). The cumulative run-time of all but the last few iterations depends exponentially on the number of iterations; one can then bound the time required for all but the last few iterations by something like O( log(*N*)2 ) again.
This is then an upper bound for the whole procedure.


**Remark.** I doubt that one can do better than the upper bound of O( log(*N*)2 ) above. I also doubt that I'm the first person to solve this problem, and I'd rather not clutter up a paper describing this solution if I can cite another paper instead.



Reference request: given a divisor d of N, how quickly can I obtain the largest factor of N coprime to d?
Take a look at these [papers](http://cr.yp.to/coprimes.html) from Dan Bernstein. It's not quite what you are looking for, but he does even more than you need in time $n(\lg n)^{2+o(1)}$ where $n$ = number of bits of $N\cdot d$ (one of the elements of the coprime base will be $n\_2$). Maybe your problem can be solved even faster than that.


