Tomando modulo por producto de 2 primos.

Question

Si se nos da un número$n$ y dos números primos$p_1$ y$p_2$, y tenemos$a = n$ modulo$p_1$ y$b = n$ modulo$p_2$, ¿se puede evaluar$n$ modulo$p_1p_2$ usando$a$ y$b$?

Answer 1

Usted está preguntando acerca de un caso especial del Teorema del Resto Chino. (Por favor, consulte el artículo de la Wikipedia, o cualquier comienzo del libro en la Teoría de números.)

Que nos llame a los números primos $p$$q$, y se supone que son distintos. En primer lugar, encontrar los números de $s$ $t$ tal que $qs \equiv 1\pmod p$$pt\equiv 1\pmod{q}$. Para un gran$p$$q$, podemos hacerlo usando el Algoritmo de Euclides Extendido. Para las pequeñas $p$$q$, uno a menudo puede hacerlo por la inspección.

Entonces $$n\equiv aqs+bpt\pmod {pq}.$$ Ahora podemos comprobar que la expresión anterior es correcta. Tenga en cuenta que $aqs+bpt\equiv aqs \pmod{p}$. Pero por la elección de $s$,$qs\equiv 1\pmod{p}$, lo $aqs+bpt\equiv a \pmod{p}$. Del mismo modo, $aqs+bpt\equiv b \pmod{q}$.

Tenga en cuenta que una vez que hemos precalculadas $s$$t$, que puede ser utilizado por cualquier da los valores de $a$$b$.

Answer 2

La respuesta corta es que si$x \equiv x_0\ (\text{mod}\ p_0)$ y$x \equiv x_1\ (\text{mod}\ p_1)$ entonces

$$x\equiv p_0*(p_0^{-1}\ \text{mod}\ p_1)*(x_1-x_0) \hspace{1em} (\text{mod}\ p_0p_1)$$

As André has already noted, this is a consequence of the Chinese Remainder Theorem, and more directly Garner's algorithm. Garner's algorithm works by assuming $ x$ has the form $ v_0 + p_0v_1 + p_0p_1v_2 + \ dots$ and using the residues to solve for the various $ v_i$.

Concretely, if you have residues $ xs = [x_0, x_1, \ dots]$ and prime powers $ #% m = p_0 ^ {k_0} p_1 ^ {k_1} \ dots$ you may calculate $ x \ \ text {mod} \ m$ by the following simple procedure:

def garner(xs, ps, m):
    r, q = 0, 1
    for x, p^k in zip(xs, ps):
        r += q * inv(q, p^k) * (x - r)
        r %= m
        q *= p^k
    return r

Where $ \ text {inv} (n, p ^ k)$ returns the inverse of $ n $ modulo $ p ^ k$. (This can easily be calculated using fast exponentiation and Euler's formula as $ n ^ {p ^ {k-1} (p-1) -1} \ \ text {mod} \ p ^ k $).