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 *x _{j}* ,

*y*, and

_{j}*g*by the recurrences

_{j}$\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 *g _{j}* = 1), we may let

*n*

_{1}=

*x*and

_{j}*n*

_{2}=

*y*.

_{j}Note that for any *j* such that *x _{j}* ≥

*y*, we may show without too much difficulty that

_{j}*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

*x*. Considering the prime-power decompositions of

_{j}*x*and of

_{j}*N*, we may note that the exponent of the maximal power of each prime

*p*dividing

*x*doubles with each succesive iteration, until it saturates the exponent of the maximal power of

_{j}*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.