# Chinese remaindering to solve solvable diophantine equations

Given a diophantine equation $$f(x_1,\dots,x_z)=0$$ where $$f(x_1,\dots,x_z)\in\mathbb Z[x_1,\dots,x_z]$$ is of total degree $$d$$ and each variable degree $$d_i$$ where $$i\in\{1,\dots,z\}$$ there is no method to solve it unless we are looking within a bound $$\|(x_1,\dots,x_z)\|_\infty

Suppose we know $$B$$ is upper bound for solution size then we know $$f(x_1,\dots,x_z)=0$$ is solvable over $$\mathbb Z^z$$ iff $$f(x_1,\dots,x_z)=0\bmod p$$ is solvable for a suitable prime $$p$$ at least of size $$f_{max,B}=\max_{\substack{(x_1,\dots,x_z)\in\mathbb Z^z\\\|(x_1,\dots,x_z)\|_\infty where $$f(x_1,\dots,x_z)=f_+(x_1,\dots,x_z)-f_-(x_1,\dots,x_z)$$ where each coefficient of $$f_+(x_1,\dots,x_z)$$ and $$f_-(x_1,\dots,x_z)$$ is non-negative (in the iff only part I meant to say only look at $$x_i:|X_i| even when considering $$\bmod p$$).

Is this the best we can do?

Can we reduce solving for $$(x_1,\dots,x_z)\in\mathbb Z^z$$ with $$\|(x_1,\dots,x_z)\|_\infty to solving $$f(x_1,\dots,x_z)=0\bmod q_i$$ for $$i\in\{1,\dots,t\}$$ such that $$\prod_{i=1}^tq_i>f_{max,B}$$ holds or is there an obstruction to getting such a 'Diophantine' Chinese Remainder Theorem?

If above is too optimistic there perhaps are there other approaches?

Reason to believe anything canonical will not easily work. Take Diophantine equation $$f(x_1,x_2)=x_1x_2-PQ=0$$ where $$P,Q$$ are primes where $$B=\lceil\sqrt{2PQ}\rceil$$. Clearly if there is a neat 'Diophantine' Chinese Remainder theorem we can break $$\mathsf{RSA}$$.

• I do not understand the "iff" part. Solutions modulo $p$ may not necessarily satisfy $\|(x_1,\dots,x_z)\|_\infty<B$, and thus they may not correspond to solutions over $\mathbb Z$. That is, solubility modulo $p$ does not seem to imply solubility over integers. – Max Alekseyev May 20 at 2:21
• @MaxAlekseyev $|x_i|<B\ll p$ and so I meant to say solvable with $|x_i|<B$ even with mod $p$. For example $XY-PQ\equiv0\bmod p$ where $p\gg PQ$ and $|X|,|Y|<\lceil\sqrt{2PQ}\rceil$ should still solve factoring. The $\bmod p$ is not relevant nor analogous to Hasse principle. The problem is more of combinatorial flavor than arithmetic. I am just wondering if the obstructions that occur can be made explicit so that one might look for work around in applicable situations. – VS. May 20 at 2:42