Autor Tema: Ecuación aritmética modular

0 Usuarios y 2 Visitantes están viendo este tema.

31 Mayo, 2016, 12:06 am
Leído 2140 veces

daniiy

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 858
  • Karma: +0/-0
  • Sexo: Masculino
Hola

\( 14 = 3^x mód 17 \)

Hay alguna manera de alcanzar la solución sin ser por tanteo?

Saludos

31 Mayo, 2016, 12:39 am
Respuesta #1

Von Damian

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 168
  • Karma: +0/-0
  • Sexo: Masculino
Buenas noches.

\( 14\equiv{-3} mod 17 \). Entonces debemos encontrar \( x \) verificando \( 3^x +3\equiv{0}\hspace{0.1cm} mod 17 \), sacando factor común, debemos encontrar \( x \) verificando \( 3(3^{x-1}+1)\equiv{0}mod 17 \) Como 17 es primo \( \mathbb{Z}_{17} \) es cuerpo, por lo tanto íntegro. Además el indicador de euler de 17 es 16 (por ser primo) y es el orden del grupo de los invertibles en \( \mathbb{Z}_{17} \). Por lo tanto  que se verifique la anterior igualdad \( 3^{x-1}+1\equiv 0 mod 17 \) es equivalente a que se verifique  \( 3^{x-1}\equiv -1\hspace{0.1cm} mod 17\hspace{0.1cm}\equiv  \hspace{0.1cm}16\hspace{0.1cm} mod 17 \) Y tomando x=9 sale fácilmente.

Editado: como 16 es el indicador de Euler se verifica que  todo elemento de \( \mathbb{Z}_{17} \) elevado a 16 \( \equiv{1}\hspace{0.1cm} mod 17 \)

Editado 2: Este tipo de problemas es un de los pilares básicos en criptografía, se llaman logaritmos discretos y no hay ningún algoritmo computacional  que trate el problema. Por lo tanto paciencia y boli.

Espero haberte ayudado  ;)

31 Mayo, 2016, 01:02 am
Respuesta #2

daniiy

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 858
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias! Sí, justo ese problema lo tengo en un ejercicio de criptografía jajja, pues bueno, me tocará ir probando hasta dar con la solución en ese caso!

Un saludo

31 Mayo, 2016, 01:05 am
Respuesta #3

Von Damian

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 168
  • Karma: +0/-0
  • Sexo: Masculino
Mi recomendación es que antes de ponerte a echar cuentas intentes simplificar al máximo la ecuación modular. 

31 Mayo, 2016, 01:07 am
Respuesta #4

daniiy

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 858
  • Karma: +0/-0
  • Sexo: Masculino
Mi recomendación es que antes de ponerte a echar cuentas intentes simplificar al máximo la ecuación modular. 
Tomo nota, muchas gracias :)