Encontrar el módulo de una fracción

Question

En el contexto de la criptografía, necesito encontrar la clave privada de un mensaje y necesito utilizar la aritmética modular. Entiendo cómo funciona la aritmética modular usando un reloj con números enteros. Pero realmente me atasco cuando llego a las fracciones, por ejemplo:

1/3 mod 8

¿Cómo encuentro el módulo de una fracción? ¿Existe un método para encontrar esto?

¡Gracias de antemano!

Answer 1

Escribir fracciones como $\frac{1}{3} \pmod{8}$ es lo mismo que escribir $3^{-1} \pmod{8}$ que es el inverso de $3$ módulo $8$.

En otras palabras, cuando escribes $\frac{a}{b} \pmod{n}$ te estás refiriendo a un número $k$ tal que $bk \equiv a \pmod {n}$ pero debes prestar atención a que esta fracción está definida si y solo si $\gcd(b,n)=1$. En otras palabras, el denominador debe ser coprimo al módulo.

Para encontrar a qué número módulo $n$ representa esta fracción, necesitas evaluar $b^{-1}$. Puedes hacerlo usando el algoritmo de Euclides para resolver la ecuación de Bézout $bx + ny = 1$. El $x$ en esta ecuación te dará $b^{-1}$. Si conoces la factorización de $n$ también puedes usar la función totient de Euler notando que $b^{-1} \equiv b^{\varphi(n)-1} \pmod{n}$. Después de saber cuál es $b^{-1}$ verás que $k \equiv a \dot b^{-1} \pmod {n}$.

Answer 2

n  ≡ (1/3)  (mod 8)
3n ≡ 1      (mod 8)
prueba n= 1,2,3
  cuando n=1, 3 mod 8 es 3
  cuando n=2, 6 mod 8 es 6
  cuando n=3, 9 mod 8 es 1, (esta es nuestra respuesta)

Entonces, la respuesta es 3

Este método se puede usar para cualquier fracción. Otro ejemplo: 2/5 mod 3

 5n mod 3 = 2
 prueba grupo de {0, 1, 2} que satisfacen lo anterior,

resultado n=1

Answer 3

La propiedad importante de $1/3$ es que $1/3 \cdot 3 = 1$. Entonces, ¿qué número, al ser multiplicado por $3$, es $1$ módulo $8$?

Mostrar cuándo $x^{-1} \pmod n$ existe y que es único tampoco es tan terrible

EDITAR: No vi "encontrándolo". Echa un vistazo al algoritmo extendido de Euclides.

Answer 4

Calculando el módulo 8, tenemos $\frac{1}{3} = \frac{3}{9} = \frac{3}{1} = 3$.

Answer 5

La definición de $$x\mod y=x-y\left\lfloor \frac xy\right\rfloor, \lfloor x+yi\rfloor=\lfloor x\rfloor +i\lfloor y\rfloor$$

lo cual casi parece que los $y$ se pueden cancelar y luego los $x$

A continuación, sustituir $\left(\frac13,8\right)$

Por lo tanto: $$\frac13\mod 8=\frac13-8\left\lfloor \frac {\frac13}8\right\rfloor=\frac13-80=\frac13$$

De hecho:

$$x\mod y=x-y\left\lfloor \frac xy\right\rfloor,\mathop=^{0\le\frac xy<1}x-y 0=x$$

Aquí hay $32$ otras formas cerradas de la función Módulo. ¡Por favor corríjame y déme retroalimentación!