4 votos

Sistema de ecuaciones modulo de los números primos

Es generalmente posible resolver un conjunto de ecuaciones lineales modulo algunos números primos $\{p,q,r\}$. Por ejemplo, si tengo las siguientes congruencias:

$$ xa_p + yb_p \equiv d \pmod {p}\\ xa_q + yb_q \equiv d \pmod {p}\\ xa_r + yb_r \equiv d \pmod {r}\\ $$

para algunas de las $a_i$ $b_i$ $i \in \{p,q,r\}$ puedo determinar $d$ (suponiendo que existe una solución y $d<p,q,r$)?

Gracias de antemano! (y lo siento si esto es trivial.)

EDIT: Además, $a_i$ $b_i$ son congruencias de un desconocido (y grandes) enteros $a,b$. (es decir,$a\equiv a_i \pmod{i}$$b\equiv b_i \pmod{i}$ )

Los punteros son bienvenidas! También sabiendo que no hay una "buena" algoritmo para este problema también me ayudan mucho.

1voto

jmans Puntos 3018

Ya que el problema es finito, una aproximación de fuerza bruta va a encontrar una solución o demostrar que no existe ninguno. En más detalle, si $x,y$ es una solución, entonces se $x+kpqr,y+spqr$ es una solución para todos los $k,s\in \mathbb Z$ (desde $pqr=0$ modulo cada una de las $p,q,r$). Es por lo tanto de la siguiente manera (mediante el algoritmo de la división) que si existe una solución, entonces existe una solución con $x,y\in \{0,1,\cdots ,pqr-1\}$. Así, la aproximación de fuerza bruta será para iterar sobre todos los $0\le x,y< pqr$ y buscar soluciones. Si uno se encuentra a continuación, usted encuentra uno, de lo contrario no existe ninguno.

1voto

Foo Barrigno Puntos 730

Me gustaría echar un vistazo a este artículo en el que detalla un CRT algoritmo en varias variables. Sin embargo, se busca en un algoritmo específico - el uso de una conocida de $d$ a resolver para$x$$y$. Puede ser un buen punto de partida.

-1voto

user212764 Puntos 1

x+y ≡ d (mod p)

d ≡ x (mod p)) + (y (mod p)) (mod p)

Ejemplo:

un ≡ 1 mod 3, b ≡ 2 mod 3, a + b ≡ 3 mod 3 ≡ 0,

También:

xa ≡ d (mod p), d = c (mod p),

c = a (mod p) fib (a (mod p) > x (mod p) o a (mod p) = x (mod p) O a (mod p) = 0) c = x (mod p) fib (x (mod p) > a (mod p) o x (mod p) = a (mod p) O a (mod p) = 0)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X