8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What happens to the large equation if you solve it modulo such a prime $p$ that $p\mid b$? In other words, does it fail in a manner that would allow you to reliably deduce that you have found a prime factor of the denominator? $\endgroup$ – Jyrki Lahtonen Mar 29 '18 at 5:07
  • $\begingroup$ The linear system will become singular. But I'm considering this case as so unlikely that it's not worth considering. $\endgroup$ – NovaDenizen Mar 29 '18 at 16:05
2
+50
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Sorry, need a small notation clarification. By $\mathbb{Z}(P,0)$ do you mean the set of all integer multiples of the vector $(P,0)$, and by $\oplus$ you mean Minkowski addition? $\endgroup$ – NovaDenizen Apr 3 '18 at 16:26
  • $\begingroup$ yes, $\mathbb{Z}(P,0)$ are integer multiples of the vector $(P,0) \in \mathbb{R}^2$. The sum is just the $\mathbb{Z}$-module (abelian group) generated by the two vectors $(P,0)$ and $(\lambda,1)$, and since this is a free module with basis this two vectors, I wrote it with $\oplus$ $\endgroup$ – user120527 Apr 3 '18 at 16:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.