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.

  • $\begingroup$ 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? $\endgroup$ May 6 '10 at 18:25
  • $\begingroup$ @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. $\endgroup$ May 6 '10 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.

  • $\begingroup$ +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. $\endgroup$ May 6 '10 at 17:58
  • $\begingroup$ I've asked a follow-up question on CS-Theory, about if there is a more complete version of Bernstein's draft "Faster factorization into coprimes". Interesting articles, thanks again. $\endgroup$ Nov 29 '10 at 11:54
  • $\begingroup$ @Niel: You're welcome! And good luck with your question at cstheory! $\endgroup$
    – Someone
    Nov 29 '10 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.

  • $\begingroup$ +1 Nice approach! Much simpler to bound than my approach above, if one uses non-naive multiplication algorithms. (Which I neglected to consider.) $\endgroup$ May 6 '10 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.