Is it possible to find the least common divisor of a two numbers that are not relatively prime in polynomial time? As the question states:
Is it possible to find the least common divisor of two number that are not relatively prime in polynomial time? If so, how?
Thanks!
 A: In short, the answer is no. There is a heuristic why it should be hard in general. Namely, the least common divisor divides the greatest common divisor. The greatest common divisor is calculable in log time. We then would want to calculate the smallest divisor $> 1$ of the gcd. But if the gcd is a hard to factor number, we're out of luck.
More generally, if we had such a technique, then we would also be able to factor in polynomial time. While this might yet be possible (in the sense that we haven't proved it's impossible), it's not likely and certainly not currently known. As Andre Nicolas said in the comments, we would apply the least-common-divisor operator to $(N,N)$, which would spit out a factor. Repeating, we could completely factor $N$.
As an aside, it is sometimes common for factoring algorithms to take the gcd of $N$ and the product of the first $40$ primes or so, to get all the small primes out of the way. This is fast, and so we can find small prime divisors quickly. But this is a different question.
