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<B.$$

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<B}}\big|f_+(x_1,\dots,x_z)+f_-(x_1,\dots,x_z)\big|$$ 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|<B$ 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<B$$ 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}$.

  • $\begingroup$ 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. $\endgroup$ – Max Alekseyev May 20 at 2:21
  • $\begingroup$ @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. $\endgroup$ – VS. May 20 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.