Foros de matemática
15/12/2017, 02:54:09 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Resolver una ecuación cuadrática módulo 127  (Leído 358 veces)
0 Usuarios y 1 Visitante están viendo este tema.
francoz
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 19


Ver Perfil
« : 18/06/2017, 01:10:09 pm »

Hola a todos, soy nuevo en el foro. Estoy con un pequeño problema que no puedo resolver.
La cuestion es asi:

Sea x E N; 0 < x < 127;

Existe algún x tal que:

127 divida a ((x^2) - 2)

Determine cuales son los posibles x que cumplan tales condiciones.


Alguien sabe como resolver esto de manera analítica? Es decir utilizando algún teorema o algún razonamiento.
La verdad lo veo y no se me ocurre nada 
No se si seré yo que estoy ciego o qué.

Espero que alguien pueda echarme una mano.

Saludos!  :sonrisa_amplia:

Titulo modificado, conforme a las reglas:

De "Alguien puede resolver esto?" a "Resolver una ecuación cuadrática módulo 127"

En línea
Ignacio Larrosa
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.722


Ver Perfil WWW
« Respuesta #1 : 18/06/2017, 02:25:24 pm »

Hola a todos, soy nuevo en el foro. Estoy con un pequeño problema que no puedo resolver.
La cuestion es asi:

Sea x E N; 0 < x < 127;

Existe algún x tal que:

127 divida a ((x^2) - 2)

Determine cuales son los posibles x que cumplan tales condiciones.


Alguien sabe como resolver esto de manera analítica? Es decir utilizando algún teorema o algún razonamiento.
La verdad lo veo y no se me ocurre nada 
No se si seré yo que estoy ciego o qué.

Espero que alguien pueda echarme una mano.

Saludos!  :sonrisa_amplia:

Titulo modificado, conforme a las reglas:

De "Alguien puede resolver esto?" a "Resolver una ecuación cuadrática módulo 127"



Hola francoz, bienvenido al foro. Parece claro que no has leido las reglas, dedica unos minutos a este enlace: Lectura obligada antes de postear por primera vez

En cuanto a tu problema, se trata de saber si [texx]2[/texx] es o no un resto cuadrático [texx]\mod 127[/texx]. Para esto en Teoría de números se suele utilizar el símbolo de Legendre:

[texx](n\,|\,p)=\begin{cases} +1 & \text{si}& n\textrm{ SI es un resto cuadrático módulo }p\\-1 & \text{si}& n\textrm{ NO es un resto cuadrático módulo }p\end{cases}[/texx]

donde [texx]p[/texx] es un primo impar y [texx]n\neq{}0\; (\textrm{mod } p)[/texx]. Si [texx]n = 0\; (\textrm{mod } p)[/texx], se define [texx](n\,|\,p)=0[/texx]
Para calcular los símbolos de Legendre se puede aplicar el criterio de Euler:

[texx](n\,|\,p) = n^{\dfrac{p-1}{2}} (\textrm{mod }p)[/texx]

Pero en el caso particular de lo símbolos [texx](2\,| p)[/texx], se puede halla más directamente así:

[texx](2\, |\, p) = (-1)^{\dfrac{p^2-1}{8}} = \begin{cases} +1 & \text{si}& p = \pm{}1 \textrm{ mod }8\\-1 & \text{si}&  p = \pm{}5 \textrm{ mod }8\end{cases}[/texx]

Como [texx]127 = -1 (\textrm{ mod }8)[/texx], tenemos que [texx](2 \,|\,127) = 1[/texx] y tu ecuación tiene soluciones, exactamente dos, opuestas [texx]\textrm{mod }p[/texx].

Todo esto puedes verlo por ejemplo en Residuo cuadrático

Otra cosa es hallar las soluciones, no es un problema sencillo. Aquí describen un algoritmo: RAIZ CUADRADA MODULAR CUANDO N ES NUMERO PRIMO.

No obstante, par un número relativamente pequeño como 127, se acaba antes ensayando todos los candidatos [texx]1 \ldots 63[/texx]. Con lo que se obtiene rápidamente la respuesta [texx]x = 16[/texx]. La otra solución es entonces [texx]x = 111[/texx].

Saludos,



En línea

Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por mucho menos ...
Ignacio Larrosa
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.722


Ver Perfil WWW
« Respuesta #2 : 18/06/2017, 02:37:07 pm »


Claro que este caso es mucho más simple, teniendo en cuenta que [texx]127 = 2^7 - 1[/texx]. Basta multiplicar por 2, para obtener:

[texx]2\cdot{}127=2^8 - 2 = (2^4)^2 - 2[/texx]

Por tanto [texx]x = 2^4 = 16[/texx] es una solución, la otra es [texx]-16 = 111\; (\textrm{mod }127)[/texx]. Al ser [texx]127[/texx] primo no hay otras. Si [texx]p[/texx] es primo, la mitad de los restos [texx]\textrm{mod }p[/texx] tienen dos raíces cuadradas, y los otros ninguna.

Saludos
En línea

Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por mucho menos ...
francoz
Junior
**

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 19


Ver Perfil
« Respuesta #3 : 18/06/2017, 03:25:27 pm »


Claro que este caso es mucho más simple, teniendo en cuenta que [texx]127 = 2^7 - 1[/texx]. Basta multiplicar por 2, para obtener:

[texx]2\cdot{}127=2^8 - 2 = (2^4)^2 - 2[/texx]

Por tanto [texx]x = 2^4 = 16[/texx] es una solución, la otra es [texx]-16 = 111\; (\textrm{mod }127)[/texx]. Al ser [texx]127[/texx] primo no hay otras. Si [texx]p[/texx] es primo, la mitad de los restos [texx]\textrm{mod }p[/texx] tienen dos raíces cuadradas, y los otros ninguna.

Saludos

Hola, muchísimas gracias por todo!
De verdad me ha servido mucho tu ayuda.

Primero que nada, perdón por lo del título.
Con respecto al tema, solo tengo una duda. Teniendo la misma ecuación, si p no es primo y no conozco su factorización, ¿puedo hallar cuantas soluciones tiene la ecuación?.
O mejor aún, dejando de lado si p es primo o no, ¿se puede conocer la cantidad de soluciones de la ecuación?

Saludos!
En línea
Ignacio Larrosa
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 1.722


Ver Perfil WWW
« Respuesta #4 : 18/06/2017, 03:39:37 pm »

Con respecto al tema, solo tengo una duda. Teniendo la misma ecuación, si p no es primo y no conozco su factorización, ¿puedo hallar cuantas soluciones tiene la ecuación?.
O mejor aún, dejando de lado si p es primo o no, ¿se puede conocer la cantidad de soluciones de la ecuación?

No, y eso está muy relacionado con la dificultad de romper la encriptación RSA. Si [texx]m[/texx] es un entero impar con [texx]n[/texx] factores primos distintos, para cada factor primo de [texx]m[/texx] hay dos raíces cuadradas o ninguna. Si hay raíces cuadradas para todos, via Teorema Chino del Resto se determinan [texx]2^n[/texx] raíces cuadradas [texx]\textrm{mod }m[/texx]. Pero como ves, es imprescindible conocer la factorización de [texx]m[/texx].

Saludos,
En línea

Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por mucho menos ...
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!