Fast way to check if two integers don't have any prime factors in common

Question

I would like to know if two integers $a$ and $b$ have at least one prime factor in common. I know calculating the GCD (by e.g. the Euclidean algorithm) would produce the right answer. However since I only care about any factor and not necessarily the largest, can it be done faster?

Answer 1

This is equivalent to a fast method for detecting coprimality. (Two numbers are coprime if their GCD is $1$.) If there is a faster way to detect that their GCD is ${}>1$, without actually computing it, this is the method that would be used to detect coprimality. The current fastest method to detect coprime pairs of numbers is to compute their GCD, so there is currently no faster way known to do what you ask.

One could reduce both numbers modulo a few small primes -- this could detect a common factor without computing a GCD. And if your numbers are "randomly" chosen, then having a small factor is not rare. ($1/4$ randomly chosen pairs of integers (of some a priori bounded length) have a common factor of $2$, $1/9$ have a common factor of $3$, $1/25$ have a common factor of $5$. Summing all the squares of reciprocals of primes, we expect $45.224\dots\%$ of pairs of integers to have a common factor.) But GCDs are fast -- the same amount of time would not allow testing very many candidate prime divisors.

The time to compute the GCD of $m$ and $n$ is proportional to the time to multiple $m$ by $n$, so you expect to have time to test a small multiple of $\log (\min\{m,n\})$ primes before you spend more time on testing than on computing the GCD. Pretending the "small multiple" is $1$, this means you get to test as many primes as the number of digits in the smaller of $m$ and $n$. So for $100$ digit numbers, you only have time to test $100$ small primes before you can compute the GCD. Note that a real computer will have a different value of "small multiple" than $1$. The computer I'm typing this on takes $284\,\mu \mathrm{s}$ to test the first $100$ primes on $m,n$ pairs having $100$ digits and $6 \, \mu \mathrm{s}$ to compute their GCDs. So on this computer, that small multiple is around $1/50$. As I say, GCDs are fast.

---

Changed in edit: The first timings posted combined the time to generate the $m$ and $n$ pairs with the time to test primes or to compute GCDs. During the runs, generating the pairs was taking about $6\,\mu \mathrm{s}$. Consequently, both timings were reduced by the time to generate the pairs. This changed the "small multiple" from $1/20$ to $1/50$ since it roughly halved the time spent on GCDs.