Given finite field projections of a rational, can I find the original rational?

Question

If you don't know a particular integer $a$, but you know several residues ($r_i$) of $a$ modulo several mutually prime integers ($m_i$), you can use the Chinese Remainder Theorem to find $r$ such that $a = r + k\prod{m_i}$, varying over $k$, with $0 \le r < \prod{m_i}$. If you know $0 \le a < \prod{m_i}$, then you have $a = r$.

Every rational number $a/b$ can be projected onto a prime finite field $\mathbb{Z}/\mathbb{Z}_p$ (given that $b$ is invertible, i.e. $\gcd(p,b) = 1)$, for many $p$.

Given a collection of these projections, $i$ pairs $(r_i, p_i)$ where $a/b \equiv r_i \mod p_i$, is there some process similar to the Chinese Remainder Theorem by which you can take that collection of pairs and work backwards to find $a/b$?

For example, given the list of pairs $[(2,3), (3,5), (6,11), (500000004, 1000000007)]$, can you work backwards to find $1/2$?

I realize that there will always be an infinity of integer and rational solutions for every collection of residues, but there will always be a smallest solution corresponding to the $0 \le r < \prod{m_i}$ above, perhaps a $a/b$ minimizing $|ab|$ or $a^2b^2$, and I would like to find that.

If you need to, add in the ability to generate new residues for arbitrary given primes instead of working from a fixed input collection of pairs. These rational numbers I'm trying to solve for are solutions to some large linear equations, and these equations are convenient to solve over "small" finite fields ($p \le 2^{32}$), but inconvenient to solve over infinite-precision rationals.

Answer 1

You may do the following, although I did not try explicitly on any example.

Assume we are given congruences $(r_i,p_i)$. Write $P=\prod p_i$.

First, find a integer solution $\lambda \in \mathbb{Z}$ to the congruences $\lambda\equiv r_i \mod p_i$.

Then $\lambda/1$ is a fraction satisfying the congruences, but it's not very interesting since $\lambda$ is usually as big as $P$. If $(a,b)$ is such that $b$ is coprime to $P$ and $a/b\equiv \lambda \mod P$, then $a\equiv b\lambda \mod P$. So let's have a look at the set $$\Lambda=\{(a,b)\in \mathbb{Z}^2 \, : \, a\equiv b\lambda \mod P\}.$$ The question, as I understand it, is to find a nonzero element $(a,b)$ of $\Lambda$, of small norm.

We may notice that $\Lambda=\mathbb{Z}(P,0)\oplus \mathbb{Z}(\lambda,1)$. So this is a lattice in $\mathbb{Z}^2$ of covolume $P$. By Minkowski's Theorem, there exist a nonzero vector of norm $\leq 2\sqrt{P/\pi}$.

Now, since the dimension is two, there exists very reasonable algorithms to find the shortest nonzero vector of a lattice (the so-called shortest vector problem). See for example Algorithm 1.3.14 in H. Cohen, A course in computational algebraic number theory.