Reference request: given a divisor d of N, how quickly can I obtain the largest factor of N coprime to d?

Question

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₁ and n₂ , such that N = n₁n₂ , and such that d divides n₁?

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_j , and g_j 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 g_j = 1), we may let n₁ = x_j and n₂ = y_j .

Note that for any j such that x_j ≥ y_j , we may show without too much difficulty that g_j+1 = 1; so the last few iterations take time O( log(N)² ), and the time required for the preceding iterations increases monotonically with x_j . Considering the prime-power decompositions of x_j and of N, we may note that the exponent of the maximal power of each prime p dividing x_j 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)² ) 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)² ) 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.

Answer 1

Take a look at these papers 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.

Answer 2

Another approach would be to take the gcd of $N$ and a large power $p^k$ of $p$. This would give $n_1$. In a worst case scenario, $k$ could be $\lg N$, but usually you wouldn't need anything this big. You save time by computing $a\equiv p^k$ (mod $N$) and then computing $\gcd(a,N)$ by the Euclidean algorithm.