Qué es la aritmética del módulo

Question

Estoy tratando de entender qué significa mod en esta ecuación y cómo resolverla:

d * 13 = 1 mod 1680

Esto es de cómo hacer un par de claves públicas y privadas. La respuesta es 517 aparentemente y la puedo obtener de wolfram. Supongo que mod es %, pero no parece que funcione. También he visto que esto me podría mod( 1, 1680 ) que supuestamente es igual a

mod( m, n ) = m - n ( m / n )

Pero para eso me sale 1 y entonces 1 / 13 no es obviamente 517. Solo busco alguna orientación. Gracias.

Ja, sé tan poco que ni siquiera puedo encontrar una etiqueta para añadir.

Answer 1

$a\equiv b \pmod c$ significa que

$a-b=k\cdot c$ para algún número entero $k$ Así que..:

$13d \equiv 1 \pmod {1680}$ significa que:

$13d-1=k\cdot 1680$ para algún número entero $k$

Editar:

Código de arce :

Answer 2

Pues bien, en la infancia aprendimos que 53 dividido entre 7 deja un resto de 4. En aritmética modular, lo escribimos como $53\equiv4 \mod 7$ . Dado $n\equiv k \mod j$ lo interpretamos como $j$ divide $(n-k)$ o $j|(n-k)$ . Aquí es un enlace. Espero que le sirva de ayuda.

Answer 3

Al mismo que $a= b\,\operatorname{mod} n$ es decir que cuando se divide $a$ y $b$ por $n$ se termina con el mismo remanente. Así que, $517\cdot 13=6721$ . Dividir $6721$ por $1680$ y se obtiene un remanente de $1$ .

Answer 4

$\pmod {1680}$ significa que se consideran todos los enteros que difieren en un múltiplo de $1680$ para que sean equivalentes. Forman un anillo, lo que significa (al igual que los números enteros) que se puede sumar, restar, multiplicar y quizás dividir. Si el módulo es primo, tienes un campo y puedes dividir también. En este caso se puede dividir y $13*517=6721=4*1680+1$ Así que $13^{-1}=517.$ Podrás realizar cualquier división en la que los valores sean coprimos a $1680$ (no comparten ningún factor, que son $2,3,5,7$ ).

Answer 5

Creo que estás interpretando mal la declaración original. En efecto, en la mayoría de los lenguajes de programación, Mod es el operador binario %. Así, por ejemplo,

5 % 4 = 1

Esto implica que $$5 \equiv 1 \qquad (\text{mod } 4)$$ (Sin embargo, no es lo mismo. Véanse los comentarios de Michael Hardy más abajo).

Sin embargo, esto no te ayudará a resolver la ecuación original. Mi interpretación de tu pregunta me lleva a pensar que has intentado algo así:

(nota para quien escanee, lo siguiente es intencionadamente incorrecto)

13 * d = 1 mod 1680 = 1 % 1680 = 1

y luego concluir que d=1/13. Del mismo modo, su función mod(m,n) realiza la operación equivalente, resultando de nuevo en 1/13.

La ecuación original pregunta,

$$13 d\equiv 1 \qquad (\operatorname{mod} 1680)$$

o, ¿qué número, multiplicado por 13, equivale a 1 mod 1680? Lo primero que hay que saber es que, si 13 no divide a 1680, hay infinitos números. Lo más probable es que queramos el número positivo más pequeño para el que esto sea cierto.

Hay muchas, muchas maneras de pensar en esto. Podrías empezar a introducir números, tratando de encontrar uno que satisfaga esta condición. Si lo hicieras a mano, sería una forma terrible de hacerlo, pero si lo estás programando no te llevará mucho tiempo:

d=1
while (d * 13 % 1680 != 1):
    d++

Por otro lado, para números realmente grandes esto es bastante ineficiente. Un enfoque es reescribir tu ecuación como una equivalente (como sugirió pedja):

Si buscamos $d$ tal que $13d\equiv 1 \quad (\operatorname{mod} 1680)$ entonces estamos buscando un número $d$ tal que $13d-1=1680k$ para algún número entero $k$ . Reorganicemos eso para que sea:

$$13d-1680k=1$$

Esto es como una ecuación lineal diofantina, y se puede utilizar la Algoritmo euclidiano para resolver ecuaciones lineales diofantinas . Este enfoque es de naturaleza algorítmica, por lo que podría programarse sin duda.

Otro método sería utilizar reglas sobre el módulo para encontrar uno de esos $d$ . Este método funciona bien a mano cuando el módulo es pequeño, pero dudo que se pueda programar (fácilmente). Esto depende más de tu sentido matemático, para elegir las operaciones adecuadas que finalmente eliminarán el multiplicador de 13 en el lado izquierdo.