Dadas las proyecciones en campo finito de un racional, ¿puedo encontrar el racional original?

Question

Si no conoce un número entero en particular $a$ pero se conocen varios residuos ( $r_i$ ) de $a$ módulo de varios enteros mutuamente primos ( $m_i$ ), puedes utilizar el Teorema del Resto Chino para encontrar $r$ tal que $a = r + k\prod{m_i}$ que varía a lo largo de $k$ con $0 \le r < \prod{m_i}$ . Si sabes $0 \le a < \prod{m_i}$ Entonces, usted tiene $a = r$ .

Todo número racional $a/b$ puede proyectarse sobre un campo finito primo $\mathbb{Z}/\mathbb{Z}_p$ (dado que $b$ es invertible, es decir $\gcd(p,b) = 1)$ para muchos $p$ .

Dada una colección de estas proyecciones, $i$ pares $(r_i, p_i)$ donde $a/b \equiv r_i \mod p_i$ ¿hay algún proceso similar al Teorema del Resto Chino por el que se pueda tomar esa colección de pares y trabajar hacia atrás para encontrar $a/b$ ?

Por ejemplo, dada la lista de pares $[(2,3), (3,5), (6,11), (500000004, 1000000007)]$ ¿Puedes trabajar hacia atrás para encontrar $1/2$ ?

Me doy cuenta de que siempre habrá una infinidad de soluciones enteras y racionales para cada colección de residuos, pero siempre habrá una solución más pequeña correspondiente al $0 \le r < \prod{m_i}$ arriba, tal vez un $a/b$ minimizar $|ab|$ o $a^2b^2$ y me gustaría encontrarlo.

Si lo necesita, añada la capacidad de generar nuevos residuos para primos dados arbitrariamente en lugar de trabajar a partir de una colección de pares de entrada fija. Estos números racionales que estoy tratando de resolver para son soluciones a algunas ecuaciones lineales grandes, y estas ecuaciones son convenientes para resolver sobre campos finitos "pequeños" ( $p \le 2^{32}$ ), pero inconveniente para resolver sobre racionales de precisión infinita.

Answer 1

Puede hacer lo siguiente, aunque no lo he probado explícitamente en ningún ejemplo.

Supongamos que nos dan congruencias $(r_i,p_i)$ . Escriba $P=\prod p_i$ .

Primero, encontrar una solución entera $\lambda \in \mathbb{Z}$ a las congruencias $\lambda\equiv r_i \mod p_i$ .

Entonces $\lambda/1$ es una fracción que satisface las congruencias, pero no es muy interesante ya que $\lambda$ suele ser tan grande como $P$ . Si $(a,b)$ es tal que $b$ es coprima de $P$ y $a/b\equiv \lambda \mod P$ entonces $a\equiv b\lambda \mod P$ . Así que echemos un vistazo al conjunto $$\Lambda=\{(a,b)\in \mathbb{Z}^2 \, : \, a\equiv b\lambda \mod P\}.$$ La cuestión, según entiendo, es encontrar un elemento no nulo $(a,b)$ de $\Lambda$ de la norma pequeña.

Podemos observar que $\Lambda=\mathbb{Z}(P,0)\oplus \mathbb{Z}(\lambda,1)$ . Así que esto es un entramado en $\mathbb{Z}^2$ de covolumen $P$ . Por el Teorema de Minkowski, existe un vector no nulo de norma $\leq 2\sqrt{P/\pi}$ .

Ahora bien, como la dimensión es dos, existen algoritmos muy razonables para encontrar el vector más corto no nulo de una red (el llamado problema del vector más corto). Véase, por ejemplo, el algoritmo 1.3.14 en H. Cohen, Un curso de teoría algebraica computacional de números .