Compare magnitude of integers with limited computation

Question

I have a polynomial $f:\mathbf{Z}\to\mathbf{Z}$ and very large integers $n, x$ such that $f(n)\approx x$ (specifically, I can say that $f(n)$ is within some relatively small value $\epsilon$ of $x$). However, since $n$ is large, finding $f(n)$ is slow. To check if $f(n)=x$, I can choose $p_1,p_2,...,p_m$ such that $\prod_{i=1}^m p_i>\epsilon$ and see if $f(n)\equiv x\mod p_i$ for $i=1,...,m$. However, this doesn't let me determine if $f(n)>x$ or $f(n)<x$. I think you can solve the Chinese Remainder Theorem and indirectly use the result, but as this is quadratic with respect to the digits of $\epsilon$ (the digits of $\epsilon$ is linear relative to the digits of $n$), this isn't significantly faster if at all compared to direct multiplication with Toom-3 or Schönhage–Strassen. Is there a better approach to using limited information from $f(n)$ to compare it to $x$?

Answer 1

No. I doubt there is any good method to perform such a comparison.

I'm not aware of any method for that.

Moreover, if there was such a comparison method, then it could be used to compute $f(n)$. In particular, you could use binary search together with the hypothetical comparison method to compute the value of $f(n)$. If the hypothetical comparison method is very fast, that provides a fairly fast way to compute $f(n)$. It seems implausible that there is a faster way to compute $f(n)$ than the existing known methods. If you believe that, then it places some limits on how fast you could perform such a comparison. This is not a rigorous proof of impossibility, but hopefully it lends some evidence that it is implausible such a method exists.

An alternative approach: What you could do is compute $f(n) \bmod m$, for some modulus $m=\epsilon$ (or $m=2\epsilon$), then use that value together with $x$ to infer $f(n)$. (The exact value of $m$ will depend on what exactly you mean by saying $f(n)$ is within $\epsilon$ of $x$.) You can compute $f(n) \bmod m$ in time linear in $\deg f$ and quadratic in $\log m$. This is better than computing $f(n)$ from scratch.