MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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

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 n1 and n2 , such that N = n1n2 , and such that d divides n1?

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 n1 = xj and n2 = yj .

Note that for any j such that xj ≥ yj , we may show without too much difficulty that gj+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.

-
 There's a chance that some small prime will divide d once and N lots of times. Maybe it would be better to raise d to some huge power mod N first? – Kevin Buzzard May 6 2010 at 18:25 @Kevin: This is essentially the approach suggested by Robin, below. --- In my approach outlined above, the exponent of that prime in the divisor x_j will increase at an exponential rate, corresponding roughly to repeated squaring; the same holds for each prime factor, except that the exponents saturate at the largest powers dividing N. So my approach is really like a somewhat more cumbersome version of the same thing, in which modular arithmetic is needlessly avoided. – Niel de Beaudrap May 6 2010 at 20:44

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.

-
 +1 I didn't make the connection between coprime bases and my problem (which is obvious in retrospect), but the ability to factor into a coprime basis quickly is also excellent. I'm reading through this now. – Niel de Beaudrap May 6 2010 at 17:58 I've asked [a follow-up question](cstheory.stackexchange.com/questions/3393/…) on CS-Theory, about if there is a more complete version of Bernstein's draft "Faster factorization into coprimes". Interesting articles, thanks again. – Niel de Beaudrap Nov 29 2010 at 11:54 @Niel: You're welcome! And good luck with your question at cstheory! – Someone Nov 29 2010 at 15:10

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.

-
 +1 Nice approach! Much simpler to bound than my approach above, if one uses non-naive multiplication algorithms. (Which I neglected to consider.) – Niel de Beaudrap May 6 2010 at 17:33