Aritmética modular - Hallar la raíz cuadrada

Question

Vale pues estoy en la universidad y en los apuntes aparece este ejemplo:

// Ejemplo: Calcular la raíz cuadrada de 3 módulo 143

3 módulo 143 = 3 mod (11*13)

Luego salta a esto:

√3 (mod 11) = ± 5

√3 (mod 13) = ± 4

Utilizando el Teorema del Resto Chino, podemos calcular las cuatro raíces cuadradas como 82 126, 17 y 61.

//

El profesor nunca aclara nada a pesar de que es nuestro primer encuentro con la aritmética de los módulos. No sé de dónde sale el 4 o el 5 o el √3 . ¿Alguien puede explicarme cómo ha conseguido

√3 (mod 11) = ± 5

√3 (mod 13) = ± 4

Y también cómo utiliza esta información junto con el Teorema del Resto Chino para llegar a las raíces cuadradas. Agradecería mucho si alguien pudiera ayudarme en esto

Answer 1

En realidad hay varios conceptos diferentes aquí, así que intentaré abordarlos todos. Llegaré a la aritmética modular en un momento, pero primero un repaso:

RAÍCES CUADRADAS

Debemos saber que 25 tiene dos raíces cuadradas en aritmética ordinaria: 5 y -5.

ARITMÉTICA MODULAR RAÍCES CUADRADAS

SI la raíz cuadrada existe , hay 2 de ellos modulo un primo. Para continuar con nuestro ejemplo, 25 tiene las dos raíces cuadradas 5 y -5.

Podemos comprobarlo:

$$(-5)^2 = 25 \equiv 3\bmod 11$$ $$(5)^2 = 25 \equiv 3\bmod 11$$

Encontrar las raíces cuadradas a veces requiere un poco de ensayo y error. A menudo hay que pasar por cada valor $v$ y elevar al cuadrado (para obtener $v^2$ ) para comprobar si es equivalente a $n \bmod p$ , donde $n$ es el número cuya raíz cuadrada quieres encontrar.

MÚLTIPLES PRIMOS

De nuevo, si existe una raíz cuadrada, hay dos raíces cuadradas módulo cada primo. Por tanto, si utilizamos varios primos, puede haber más raíces cuadradas. Por ejemplo, con dos primos, hay 2 raíces cuadradas módulo del primer primo y dos raíces cuadradas módulo del segundo primo. Esto nos da $2 \cdot 2 = 4$ primos.

En general, si podemos encontrar una raíz cuadrada módulo de cada primo, hay un total de $2^n$ raíces cuadradas módulo $n$ primos.

VOLVIENDO A SU EJEMPLO

Primero podemos calcular 3 módulo 11 y 13:

$$3 \equiv 3 (\bmod 11)$$ $$3 \equiv 3 (\bmod 13)$$

Así que, módulo 11, buscamos encontrar un número que, al cuadrado, sea equivalente a 3. Si encontramos uno, sabemos que habrá otro. Así que comprobamos los números: $1^2 \equiv 1$ , $2^2 \equiv 4$ , $3^2 \equiv 9, \dots$ y encontrar que

$$5^2 = 25 \equiv 3 (\bmod 11)$$

...por lo que sabemos que también habrá otra raíz cuadrada módulo 11. Siguiendo con nuestra búsqueda, comprobamos

$$6^2 = 36 \equiv 3 (\bmod 11)$$

...así que hemos encontrado las raíces cuadradas módulo 11. Entonces continuamos este módulo 13 para encontrar eso:

$$4^2 = 16 \equiv 3 (\bmod 13)$$ $$9^2 = 81 \equiv 3 (\bmod 13)$$

Así que sabemos que nuestra raíz cuadrada es 5 o 6 módulo 11, y 4 o 9 módulo 13. Esto nos da 4 posibilidades. Entonces podemos encontrar eso:

$$82 \equiv 5 (\bmod 11), 82 \equiv 4 (\bmod 13)$$ $$126 \equiv 5 (\bmod 11), 126 \equiv 9 (\bmod 13)$$ $$17 \equiv 6 (\bmod 11), 17 \equiv 4 (\bmod 13)$$ $$61 \equiv 6 (\bmod 11), 61 \equiv 9 (\bmod 13)$$

Answer 2

Considera: x≡√3(mod11); x²≡3(mod11); x²≡3+22(mod11); x²≡25(mod11); x≡±5(mod11); Entonces, x=+-5 Se puede hacer algo similar mod 13.

Let x≡5(mod11);
x≡-5(mod11);
x≡4(mod13);
x≡-4(mod13)

A continuación, utilice el Teorema del Resto Chino para encontrar los cuatro valores de x (mod 143)

Answer 3

Módulo de trabajo $11$ utilizando los números de $0$ a $10$ , que tienen la propiedad de que sus cuadrados son de la forma $11k+3$ ? Del mismo modo, el módulo $13$ utilizando los números de $0$ a $12$ , que tienen la propiedad de que sus cuadrados son de la forma $13k+3$ ?

Answer 4

Supongamos que quieres encontrar (x)^(1/2) mod p(primo) entonces simplemente calcula (x)^((p+1)/4) mod p. como en tu caso x=3 y p=11, 3^((11+1)/4)=27= 5 mod 11. de forma similar -5 será una raíz.