# Integer values of a rational function

Suppose we are given a rational function with numerator and denominator being polynomials with integer coefficients. Is there an efficient algorithm for finding all integers arguments at which the function takes integer values?

In other words, for given polynomials $F(x)$ and $G(x)$ with integer coefficients, how to compute efficiently all such integers $m$ that $G(m)$ divides $F(m)$ ?

I've developed a rather straight forward approach to this problem at http://list.seqfan.eu/pipermail/seqfan/2010-April/004339.html but I suspect it is far from optimal.

-
The reason this problem is messy is that G(x) need not have leading coefficient a unit, so I think some factorization of integers is unavoidable. Where do you think your approach can be improved? – Qiaochu Yuan Jul 1 '10 at 16:39
I don't know what you mean by "compute efficiently", but if $F(x)$ is a constant $N$, and $G(x)=x$, then you're asking how to compute efficiently all the factors of $N$, and this is pretty tough to do efficiently for most reasonable interpretations of the word, as far as I know. – Kevin Buzzard Jul 1 '10 at 16:48
Qiaochu, Kevin, good points. Let us assume that there is small number of solutions and the size of $m$ is reasonable so that we know its complete integer factorization. The case of $G(x)=x$ and $F(x)=N$ is too extreme from this perspective. Usually, $m$ is a number with large number of divisors, only a small fraction of which leads to solutions. And I don't like the idea of brute-forcing them all. – Max Alekseyev Jul 1 '10 at 17:06
@Kevin, Qiaochu: It is still very interesting to find an algorithm with complexity exponential in coefficients but polynomial in degree. I have not seen something of this sort before. – Dror Speiser Jul 1 '10 at 18:06
cf. also my reply to MO question 66873:mathoverflow.net/questions/66873/67202#67202 – Noam D. Elkies Nov 26 '12 at 22:07