19/09/2018, 03:55:04 am *
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: Homenaje a NUMERARIUS
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Hallar las raíces  (Leído 11896 veces)
0 Usuarios y 1 Visitante están viendo este tema.
michelmarques
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10


Ver Perfil
« : 22/07/2012, 03:16:46 pm »

Hola gente!! Soy nuevo en el foro es mi primer mensaje, aunque alguna que otra vez me he documentado en el mismo. La verdad es que estoy preparando un examen de criptografía y estoy atascado en la siguiente pregunta, ...

5. Obtener las raíces de 4 mod 21

No hay forma de intuir la forma de resolverlo, así que frente a la proximidad del examen me veo forzado a recurrir a vuestra ayuda, me gustaría si pudierais que me echarais un cable.

Un saludo!
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #1 : 22/07/2012, 04:49:08 pm »

5. Obtener las raíces de 4 mod 21

¿Qué tiene que cumplir un número para ser raíz de 4 mod 21? Pregunto porque no sé la definición. Si la supiera, capaz que podría ayudarte.
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
michelmarques
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10


Ver Perfil
« Respuesta #2 : 22/07/2012, 06:00:31 pm »

5. Obtener las raíces de 4 mod 21

¿Qué tiene que cumplir un número para ser raíz de 4 mod 21? Pregunto porque no sé la definición. Si la supiera, capaz que podría ayudarte.

Ahí está el tema, que no sé que tiene que cumplir para ser raíz. Y por tanto no avanzo.

Gracias por la respuesta de todas formas.
En línea
soneu
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 801



Ver Perfil
« Respuesta #3 : 22/07/2012, 06:37:24 pm »

Quiere decir que

[texx] x^2\equiv 4 (\mbox{mod} 21).[/texx]
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #4 : 22/07/2012, 07:03:13 pm »

Quiere decir que

[texx]x^2\equiv 4 (\mbox{mod} 21).[/texx]

Muchas gracias soneu. Aunque lo lógico sería que dijera raíces cuadradas de 4 (módulo 21).

michelmarques: nota que [texx]21=3\cdot 7[/texx]. Resuelve:

[texx]\begin{align}x^2&\equiv 4\pmod{3}\\x^2&\equiv 4\pmod{7} \end{align}[/texx]

Por verificación directa, podemos concluir que [texx](1)[/texx] tiene por soluciones [texx]x\equiv 1\pmod{3}[/texx] y [texx]x\equiv 2\pmod{3}[/texx]. Las soluciones de la congruencia [texx](2)[/texx] son: [texx]x\equiv 2\pmod{7}[/texx] y [texx]x\equiv 5\pmod{7}[/texx]. Luego, las soluciones de [texx]x^2\equiv 4\pmod{21}[/texx] están dadas por los cuatro sistemas siguientes:

[texx]\left\{\begin{array}{l}x\equiv 1\pmod{3}\\x\equiv 2\pmod{7}\end{array}\qquad \left\{\begin{array}{l}x\equiv 1\pmod{3}\\x\equiv 5\pmod{7}\end{array}[/texx]

[texx]\left\{\begin{array}{l}x\equiv 2\pmod{3}\\x\equiv 2\pmod{7}\end{array}\qquad \left\{\begin{array}{l}x\equiv 2\pmod{3}\\x\equiv 5\pmod{7}\end{array}[/texx]

Usa el teorema chino del resto  :guiño:.

Saludos
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
michelmarques
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10


Ver Perfil
« Respuesta #5 : 22/07/2012, 07:30:20 pm »

Muchísimas gracias por la respuesta tan rápida y efectiva pero no acabo de entender muy bien lo de por "Verificación directa". Por otra parte y una vez obtenidos los sistemas, propones solucionarlo por el TCR, no?

Por verificación directa, podemos concluir que [texx](1)[/texx] tiene por soluciones [texx]x\equiv 1\pmod{3}[/texx] y [texx]x\equiv 2\pmod{3}[/texx]. Las soluciones de la congruencia [texx](2)[/texx] son: [texx]x\equiv 2\pmod{7}[/texx] y [texx]x\equiv 5\pmod{7}[/texx]. Luego, las soluciones de [texx]x^2\equiv 4\pmod{21}[/texx] están dadas por los cuatro sistemas siguientes:


En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #6 : 22/07/2012, 07:45:10 pm »

Resolver una congruencia módulo [texx]n[/texx] por "verificación directa" es sustituir [texx]x[/texx] por [texx]0,1,\dots, n-1[/texx] y fijarse para qué valor/es se cumple. Por ejemplo, para [texx]x^2\equiv 4\pmod{3}[/texx] vemos que:

[texx]\begin{align*}0^2&\not\equiv 4\pmod{3}\\1^2&\equiv 4\pmod{3}\\ 2^2&\equiv 4\pmod{3}\end{align}[/texx]

Por lo tanto, 1 y 2 soluciones distintas. Este procedimiento sirve cuando [texx]n[/texx] no es muy grande. Si en vez de 3 fuera 47 sería poco práctico. En tal caso sería más conveniente hallar una raíz primitiva módulo 47.

Saludos
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
michelmarques
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10


Ver Perfil
« Respuesta #7 : 22/07/2012, 08:17:36 pm »

Muy bien, muchas gracias, y a qué te refieres con que use el TCR (Teorema Chino del Resto)? Te refieres a que lo use para resolver los sistemas o que has realizado los sistemas mediante el TCR?

Perdona a ver si me consigo explicar, cuando me piden que diga las raíces, y sabiendo que este problema tiene 4, qué resultado he de dar? El resultado de los sistemas de ecuaciones? o dejando planteados los mismos?


Por cierto, este ejercicio estaría bien resuelto?

Obtener el menor valor [texx]x[/texx] que cumple, el siguiente sistema:

[texx]x=1[/texx] (mod [texx]3[/texx])
[texx]x=3[/texx] (mod [texx]5[/texx])
[texx]x=6[/texx] (mod [texx]11[/texx])

- 1,4,7,10,13,16,19,22,25,28,...
- 3,8,13,18,23,28,...
- 6,17,28

Por tanto el valor mínimo de [texx]X[/texx] sería [texx]= 28[/texx], no?

o bien:

[texx]N = -55\cdot 1 + 33\cdot 3 + 6\cdot 15[/texx]
[texx]N = -55+99+90[/texx] mod [texx]165[/texx]
[texx]N= 134[/texx] mod 165
[texx]N= 134[/texx]

(Mediante el Teorema Chino del Resto)

Perdona tanta ignorancia, pero me está costando Dios y ayuda hacerme con todo esto en tan pocos días, jeje.

Un saludo y gracias
En línea
michelmarques
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10


Ver Perfil
« Respuesta #8 : 23/07/2012, 07:53:45 am »

Ante todo muchas gracias por la atención que me estáis prestando, voy a intentar explicarme mejor para deciros cual es mi duda:

Tengamos [texx]9[/texx] mod [texx]35[/texx], entonces [texx]n = pq[/texx] --> [texx]35 = 5\cdot 7 [/texx]

[texx]x^2=9[/texx] mod [texx]5[/texx]   (1)

[texx]x^2=9[/texx] mod [texx]7[/texx]   (2)

Por verificación directa, podemos concluir que (1) tiene por soluciones  x= 3 mod 5 y x= 2 mod 5. Las soluciones de la congruencia (2)  son: [texx]x=3[/texx] mod [texx]7[/texx] y (no lo sé) .

// Duda en sacar las raíces por verificación directa según lo que me has explicado ya que, ... He encontrado una solución al ejercicio en la web y dan lo siguiente:


Pongamos [texx]n = 35 = 5 \cdot 7[/texx] y tomemos [texx]a = 9[/texx]. [texx]9[/texx] es un cuadrado modulo [texx]35[/texx] ya que [texx]3^2 = 9[/texx] mod [texx]35[/texx].
Ademas de [texx]3[/texx] tendremos tambien que [texx]17^2 = 289 = 9[/texx] mod [texx]35[/texx]. Por lo tanto, al menos tenemos las races [texx]\pm 3[/texx] y [texx]\pm 17[/texx]. De hecho no hay mas por lo que la congruencia x^2 =  9 mod 35 tiene 4 soluciones, o lo que es
equivalente. El polinomio [texx]x^2-9[/texx] tiene CUATRO raíces modulo [texx]35[/texx].

Es decir según la explicación anterior hallaba las raíces en función de p y q, aquí lo hacen en función de n, o eso es lo que yo entiendo, por tanto tengo que ir probando desde el 0 al 34? Sin saber si alguno a parte del 3 lo cumplirá?

En rojo las dudas.
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #9 : 23/07/2012, 06:48:47 pm »

Muy bien, muchas gracias, y a qué te refieres con que use el TCR (Teorema Chino del Resto)? Te refieres a que lo use para resolver los sistemas o que has realizado los sistemas mediante el TCR?

El teorema chino del residuo te permite asegurar que cada uno de los sistemas planteados en mi post anterior, tiene solución y además es única (módulo [texx]3\cdot 7=21[/texx]); pero no dice nada acerca de cómo determinar dicha solución. (*)

Perdona a ver si me consigo explicar, cuando me piden que diga las raíces, y sabiendo que este problema tiene 4, qué resultado he de dar? El resultado de los sistemas de ecuaciones? o dejando planteados los mismos?

No, has de resolverlos. Por ejemplo, éste:

[texx]\left\{\begin{array}{l}x\equiv 2\pmod{3}\\x\equiv 5\pmod{7}\end{array}[/texx]

Como [texx]x\equiv 2\pmod{3}[/texx] entonces [texx]x=2+3k[/texx]. Sustituyendo en la segunda congruencia:

[texx]\begin{align*}2+3k&\equiv 5\pmod{7}\\3k&\equiv 3\pmod{7}\\k&\equiv 1\pmod{7}\end{align}[/texx]

Luego, [texx]k=1+7h[/texx] por lo que [texx]x=2+3(1+7h)=5+21h[/texx]. Por lo tanto, la solución es [texx]x\equiv 5\pmod{21}[/texx].

Por cierto, este ejercicio estaría bien resuelto?

Obtener el menor valor x que cumple, el siguiente sistema:

x=1 (mod 3)
x=3 (mod 5)
x=6 (mod 11)

Así como está planteado no tiene sentido, ya que el conjunto de números enteros que satisfacen ese sistema de congruencias no está acotado inferiormente. Debiera decir: "obtener el menor valor de x>0 que cumple(...)". Te sugiero que sigas el procedimiento descrito más arriba.

x^2 = 9 mod 5   (1)

x^2 = 9 mod 7   (2)

Pongamos n = 35 = 5  7 y tomemos a = 9. 9 es un cuadrado modulo 35 ya que 3^2 = 9 mod 35.
Ademas de 3 tendremos tambien que 17^2 = 289 = 9 mod 35. Por lo tanto, al menos tenemos las races +-3 y +-17. De hecho no hay mas por lo que la congruencia x^2 =  9 mod 35 tiene 4 soluciones, o lo que es
equivalente. El polinomio x^2 - 9 tiene CUATRO raíces modulo 35.

Como [texx]x\equiv 3\pmod{35}[/texx] es solución trivial y [texx]a^2=(-a)^2[/texx] cualquiera sea [texx]a[/texx], concluye que [texx]x\equiv -3\equiv 32\pmod{35}[/texx] es también otra solución. Después se le ocurre probar con [texx]x=17[/texx] y da la casualidad que también verifica las dos congruencias dadas (o sea, que [texx]x\equiv 17\pmod{35}[/texx] es solución). Por la misma observación que hice antes, [texx]x\equiv -17\equiv 18\pmod{35}[/texx] también lo es. Alguien le pasó el dato de que el sistema tenía exactamente 4 soluciones. Por lo tanto, concluye que todas las soluciones han de ser: [texx]x\equiv 3\pmod{35}[/texx], [texx]x\equiv 17\pmod{35}[/texx], [texx]x\equiv 18\pmod{35}[/texx] y [texx]x\equiv 32\pmod{35}[/texx].

Dos objeciones:

1) ¿Por qué justo se le ocurrió probar con [texx]x=17[/texx]? ¿Casualidad? Imagino que no quieres que el resultado de tu parcial/examen dependa de la suerte (:risa:).

2) ¿Cómo sabía que había exactamente 4 soluciones incongruentes?

Para encontrar la respuesta a estas preguntas, y la justificación del método que propuse en mi post anterior, lee la página 37 del pdf adjunto.

Saludos

(*) Esto no es estrictamente cierto, pues la demostración del teorema (al menos la que yo conozco) es constructiva, es decir, proporciona un método para llegar a la solución. No obstante, me parece más cómodo (y más natural) proceder como indico.

* Congruencias23072012.pdf (137.91 KB - descargado 9393 veces.)
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
michelmarques
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10


Ver Perfil
« Respuesta #10 : 23/07/2012, 08:03:05 pm »

Sí sí, jajaja mirando la "suerte" que suelo tener he decidido buscar los algoritmos a utilizar y los he puesto en práctica y he llegado a las conclusiones que tu me has dicho. Para los sistemas los he resuelto con el Teorema Chino y para las raíces lo he resuelto con el Teorema de Rabin [http://valund.blogspot.com.es/2009/07/calculo-de-la-raiz-cuadrada-de-un.html], ... en unos 6 pasos sacas las raíces. (Ahí tienes el link con los pasos)

Pero, una cosita, cuando me he encontrado con lo siguiente:

sqrt(7) mod 33

al aplicar la solución no consigo ninguna de las raíces congruentes. ¿Cómo lo solucionarías? Me explico, aplicando el mismo algoritmo debería dar un buen resultado, pero por lo que sea, no es así, y me estoy volviendo loco.

Enserio tío, muchas gracias. En este foro, ¿Se puede votar positivo a los usuarios?
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #11 : 23/07/2012, 08:56:11 pm »

Pero, una cosita, cuando me he encontrado con lo siguiente:

sqrt(7) mod 33

Es idéntico. Hay que resolver la congruencia:

[texx]\begin{equation}x^2\equiv 7\pmod{33}\end{equation}[/texx]

Es equivalente a resolver el sistema:

[texx]\left\{\begin{array}{l}x^2\equiv 7\equiv 1\pmod{3}\\x^2\equiv 7\pmod{11}\end{array}[/texx]

Como [texx]x^2\equiv 7\pmod{11}[/texx] no tiene solución, tampoco la tiene la congruencia [texx](1)[/texx]. Por lo tanto, no existe raíz cuadrada de 7 módulo 33.

Enserio tío, muchas gracias. En este foro, ¿Se puede votar positivo a los usuarios?

Que yo sepa, soy demasiado joven para ser tu tío (:risa:). No se puede votar positivo a los usuarios. De todas maneras, no hay mejor premio para mí que tu agradecimiento  :guiño:.

Espero haberte ayudado.

Saludos
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
michelmarques
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10


Ver Perfil
« Respuesta #12 : 23/07/2012, 09:23:27 pm »

Muy bien, muchas gracias. Aplauso Aplauso Aplauso

Y hay alguna manera o teoría para saber a simple a vista si tiene o no solución? Me refiero, por ejemplo si (1) no tiene solución, ya sabemos que no tiene solución? O tengo que hallar la p y q, para ver si en los los módulos más pequeños tienen solución?
En línea
pierrot
pabloN
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 3.311


Ver Perfil
« Respuesta #13 : 23/07/2012, 11:21:31 pm »

Muy bien, muchas gracias. Aplauso Aplauso Aplauso

De nada.

Y hay alguna manera o teoría para saber a simple a vista si tiene o no solución? Me refiero, por ejemplo si (1) no tiene solución, ya sabemos que no tiene solución? O tengo que hallar la p y q, para ver si en los los módulos más pequeños tienen solución?

Es que uno se da cuenta si [texx](1)[/texx] tiene solución o no, estudiando las congruencias que resultan de factorizar el módulo. Para ello, puedes usar que una congruencia de la forma [texx]x^n\equiv a\pmod{p}[/texx] donde [texx]p>2[/texx], tiene solución en [texx]U(p)[/texx] si y sólo si [texx]\displaystyle a^{\frac{p-1}{d}}\equiv 1\pmod{p}[/texx] donde [texx]d=\big(n,\varphi(p)\big)[/texx]. Salvo algún caso excepcional no creo que haya una forma más sencilla de determinar si hay o solución o no.

Saludos
En línea

$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print
michelmarques
Nuevo
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10


Ver Perfil
« Respuesta #14 : 25/07/2012, 01:34:10 pm »

Bueno Pablon, muchas gracias por todo de verdad, y espero que el Post ayude a más gente. Un saludo.
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

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