Calculando el Inverso Multiplicativo Modular sin todos esos símbolos de aspecto extraño

Question

Estoy seguro de que todos esos símbolos son muy fáciles de entender para ustedes, pero agradecería que alguien lo bajara a la tierra por mí.

¿Cómo podría hacer esto con una calculadora básica? o con unas pocas líneas de código de programador que probablemente te parecerían extrañas :)

En particular, me costó mucho saber por qué el (mod m) estaba a la derecha y separado, y todavía no estoy seguro de qué significa el símbolo de las tres líneas. No es que me importe, pero si es simple, no me importa leerlo así, si no, preferiría las instrucciones de la calculadora.

Answer 1

"En particular, me costó mucho saber por qué el (mod m) estaba a la derecha y separado, y todavía no estoy seguro de qué significa el símbolo de las tres líneas."

La notación $(57 \equiv 62) \pmod 5$ significa que 57 y 62 son congruentes entre sí, módulo 5, es decir, ambos dejan el mismo resto al ser divididos por 5. Ver Aritmética modular . Esa notación fue introducida por Carl Friedrich Gauss en su libro Disquisitiones Arithmeticae publicado en 1801, y ha sido estándar desde entonces.

Más tarde, cuando los programadores informáticos empezaron a hacer aritmética modular, introdujeron una nueva notación: $57 \bmod 5$ significa el resto cuando 57 se divide por 5.

Sólo recuerda qué notación es cuál y no los confundas entre sí.

El artículo de Wikipedia podría beneficiarse de uno o dos ejemplos concretos.

Bien, supongamos que quieres el inverso de 322 cuando el módulo es el número primo 701. Como 701 es primo, el gcd de 701 y cualquier número que no sea múltiplo de 701 es 1. Veremos que esto implica que hay una solución a la ecuación de Diofantina $701x+322y=1$ (y si el gcd fuera algo más que 1, habría una solución si en lugar de " $=1$ "ponemos" $=\text{whatever that other number is}$ ").

Así que aplica el algoritmo euclidiano, pero recuerda los cocientes. Divide 701 por 322; obtén un cociente de 2 y un resto de 57: $$ 701-2\cdot322 = [57]. $$ En el algoritmo de Euclides, a continuación dividiríamos 322 por 57, obteniendo un cociente de 5 y un resto de 37: $$ 322 - 5\cdot [57] = [37]. $$ Luego divide 57 por 37, obteniendo un cociente de 1 y un resto de 20: $$ [57] - 1\cdot[37] = [20]. $$ Divide 37 entre 20, obteniendo un cociente de 1 y un resto de 17: $$ [37]-1\cdot[20] = [17]. $$ Divide 20 por 17, obteniendo un cociente de 1 y un resto de 3: $$ [20]-1\cdot[17]=[3]. $$ Divide 17 por 3, obteniendo un cociente de 5 y un resto de 2: $$ [17]-5\cdot[3]=[2]. $$ Dividir 3 por 2, obteniendo un cociente de 1 y un resto de 1: $$ [3] -1\cdot[2]=[1]. $$ Así que según el algoritmo de Euclides, el gcd es 1, y si eso es todo lo que queríamos, habríamos necesitado sólo los restos y no los cocientes. Pero ahora usamos los resultados anteriores para resolver $701x+322y=1$ . Esto implicará que $(322y\equiv1)\pmod {701}$ es decir, el inverso multiplicador de 322 es $y$ cuando el módulo es 701.

He puesto corchetes alrededor de los números que se encuentran como RESTANTES pero no alrededor de los CUPONES.

En lugar del 2 restante, en la última línea, pero la expresión resultó ser igual a 2 en la línea anterior: $$ \begin{align} [3]-1\cdot[2] & = [1] \\ {[}3{]}-1([17]-5\cdot[3]) & = [1] \end{align} $$ Simplifica, obteniendo una combinación lineal de RESTANTES: $$ 6[3]-1[17] =1. $$ Ahora, en lugar de los 3 restantes, pon la expresión encontrada para ser igual a ella: $$ 6([20]-1[17])-1[17] = 1. $$ Simplifica, obteniendo una combinación lineal de RESTANTES: $$ 6[20]-7[17] = 1. $$ Ahora, en lugar de los 17 restantes, pon la expresión encontrada para ser igual a ella: $$ 6[20] - 7([37]-1[20])=1. $$ Simplifica, obteniendo una combinación lineal de RESTANTES: $$ 13[20]-7[37]=1. $$ Ahora, en lugar de los 20 restantes, pon la expresión encontrada para ser igual a ella: $$ 13([57]-1[37])-7[37]=1. $$ Simplifica, obteniendo una combinación lineal de RESTANTES: $$ 13[57]-20[37]=1. $$ Ahora, en lugar de los 37 restantes, pon la expresión encontrada para ser igual a ella: $$ 13[57]-20(322-5[57])=1. $$ Simplifica, obteniendo una combinación lineal de RESTANTES: $$ 113[57]-20[322]=1. $$ Ahora, en lugar de los 57 restantes, pon la expresión encontrada para ser igual a ella: $$ 113([701]-2[322])-20[322]=1. $$ Simplifica, obteniendo una combinación lineal de RESTANTES: $$ 113[701]-246[322]=1. $$ POR LO TANTO $(-246\cdot322\equiv1) \pmod{701}$ .

O en otras palabras $(455\cdot322 \equiv1)\pmod{701}$ .

Así que el módulo 701, el inverso multiplicador de 322 es 455.

Answer 2

Aquí está el viejo código JS que tenía para computar el inverso modular de a con respecto al módulo m basado en una modificación del algoritmo euclidiano habitual. Debo admitir que he olvidado la procedencia de este algoritmo, así que agradecería que alguien me indicara dónde apareció esta modificación por primera vez:

function modinv(a,m) {
    var v = 1;
    var d = a;
    var u = (a == 1);
    var t = 1-u;
    if (t == 1) {
        var c = m % a;
        u = Math.floor(m/a);
        while (c != 1 && t == 1) {
               var q = Math.floor(d/c);
               d = d % c;
               v = v + q*u;
               t = (d != 1);
               if (t == 1) {
                   q = Math.floor(c/d);
                   c = c % d;
                   u = u + q*v;
               }
        }
        u = v*(1 - t) + t*(m - u);
    }
    return u;
}

Answer 3

Considere el elemento $a \in \mathbb{Z}/m\mathbb{Z}$ . No es difícil demostrar que $a^{-1}$ existe en $\mathbb{Z}/m\mathbb{Z}$ si y solo si el gcd de $a$ y $m$ es 1, es decir, $a$ y $m$ son coprimas. Usando el teorema de Euler (también llamado a veces teorema de Fermat), $a^{\varphi(m)} \equiv 1 \pmod{m}$ para todos $a$ coprimo a $m$ donde $\varphi(m)$ es La función totient de Euler . Por lo tanto $$a^{-1} \equiv a^{\varphi(m) - 1} \pmod{m}.$$

Así que supongo que un pseudo-algoritmo para calcular el inverso de $a \in \mathbb{Z}/m\mathbb{Z}$ podría ser:

1. Calcule el CDG de $a$ y $m$ . Si esto no es igual a 1, salga. Si no, continúe.
2. Computación $\varphi(m)$ . Una forma es contar el número de enteros menos que $m$ relativamente primo a $m$ otra forma es usar $m$ la factorización principal. Hay otras formas mucho más rápidas, pero estos dos métodos son los más obvios.
3. Computación $a^{\varphi(m) - 1}$ .
4. Reducir mod $m$ .
5. Repita el paso 4 hasta que el resultado esté en $\{0, 1, \ldots, m - 1\}$ .

Answer 4

No es necesario entender la aritmética de congruencia para entender la algoritmo euclidiano extendido aplicado a la computación de inversiones modulares. Por La identidad de Bezout hay números enteros $\rm\:x,y\:$ de tal manera que $\rm\:m\ x + n\ y\:=\:gcd(m,n) = 1\:,\:$ es decir. $\rm\ n\ y = 1 - m \ x\:.\:$ Así que, mod $\rm\:m\!:\ n\ y = 1\ \Rightarrow\ y = 1/n\:.\:$ Para calcular $\rm\:x,y\:$ se puede utilizar una forma extendida del algoritmo euclidiano que es análoga a la eliminación por aumento de identidad en el álgebra lineal, por ejemplo, véase a continuación de uno de mis antiguos posts.

For example, to solve  m x + n y = gcd(m,n) one begins with
two rows  [m   1    0], [n   0    1], representing the two
equations  m = 1m + 0n,  n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,

Here is an example:  d =  x(80) + y(62)  proceeds as:

                      in equation form   | in row form
                    ---------------------+------------
                    80 =   1(80) + 0(62) | 80   1   0
                    62 =   0(80) + 1(62) | 62   0   1
 row1 -   row2  ->  18 =   1(80) - 1(62) | 18   1  -1
 row2 - 3 row3  ->   8 =  -3(80) + 4(62) |  8  -3   4
 row3 - 2 row4  ->   2 =   7(80) - 9(62) |  2   7  -9
 row4 - 4 row5  ->   0 = -31(80) -40(62) |  0 -31  40

Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,

        row1 row2 row3 row4 row5
namely:  80,  62,  18,   8,   2  = Euclidean remainder sequence
               |    |
for example   62-3(18) = 8, the 2nd step in Euclidean algorithm

becomes:   row2 -3 row3 = row4  on the identity-augmented matrix.

In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:

         [  7 -9] [ 80  1  0]  =  [2   7  -9]
         [-31 40] [ 62  0  1]     [0 -31  40]

row 1 is the particular  solution  2 =   7(80) -  9(62)
row 2 is the homogeneous solution  0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:

       n row1 + m row2  ->  2n = (7n-31m) 80 + (40m-9n) 62

The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field, 
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form, 
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.

Answer 5

Existe un algoritmo, además del algoritmo euclidiano ampliado, que puede utilizarse para resolver

$\tag 1 ax \equiv b \pmod{p} \quad \text{where } p \text{ is prime} \land p \nmid a \land p \nmid b$

Se dio un esquema de la lógica del algoritmo aquí .

Aquí hay un programa de Python que calcula $3789 x \equiv 1234 \pmod{7919}$ ; termina con

$\tag {ANS} 3789 x \equiv 1234 \pmod{7919} \; \text{ iff } \; x \equiv 4498 \pmod{7919}$

Tomamos la salida del programa y la pegamos en nuestro intérprete Latex:

Multiplicar por $ 2 $ :

$\quad 7578 x \equiv 2468 \pmod{7919}$
$\quad -341 x \equiv 2468 \pmod{7919}$
$\quad 341 x \equiv 5451 \pmod{7919}$

Multiplicar por $ 23 $ :

$\quad 7843 x \equiv 125373 \pmod{7919}$
$\quad -76 x \equiv 6588 \pmod{7919}$
$\quad 76 x \equiv 1331 \pmod{7919}$

Multiplicar por $ 104 $ :

$\quad 7904 x \equiv 138424 \pmod{7919}$
$\quad -15 x \equiv 3801 \pmod{7919}$
$\quad 15 x \equiv 4118 \pmod{7919}$

Multiplicar por $ 528 $ :

$\quad 7920 x \equiv 2174304 \pmod{7919}$
$\quad 1 x \equiv 4498 \pmod{7919}$

Programa Python

a = 3789
b = 1234
p = 7919

while 1:
    q, r = divmod(p,a)
    s_L = q * a
    s_R = (q + 1) * a
    M = q
    left = True
    if p - s_L > s_R - p:
        M = q + 1
        left = False
    print()
    print('Multiply by $', M,'$:',)
    print()
    print('$\quad', M*a, 'x \equiv', M*b, '\pmod{7919}$<br>')
    if left:
        a = M*a - p
        b = M*b % p
        print('$\quad',a, 'x \equiv', b, '\pmod{7919}$<br>')
        a = -a
        b = -b % p
        print('$\quad',a, 'x \equiv', b, '\pmod{7919}$<br>')        
    else:
        a = M*a - p
        b = M*b % p
        print('$\quad',a, 'x \equiv', b, '\pmod{7919}$<br>')
    if a == 1:
        break

raise SystemExit