Tengo $$7^x\bmod {29} = 23 $$ Es posible conseguir $x$ probando diferentes números, pero eso no será posible si $x$ es realmente grande.
¿Hay otras soluciones para esta ecuación?
Saludos cordiales
Respuestas
¿Demasiados anuncios?
La prueba y el error es su única opción para este tipo de problemas.
El problema general se denomina logaritmo discreto, y es difícil.
Dar la primera $p$ y $a,b$ no divisible por $p,$ encontrar un número entero $x$ para que:
$$a^x\equiv b\pmod p$$
puede que ni siquiera tenga una solución. Hay una solución si y sólo si $o(b)\mid o(a),$ donde $o(c)$ es el orden multiplicativo de $c,$ el más pequeño $k>0$ tal que $c^k\equiv 1\pmod p.$
Pero incluso la informática $o(a)$ no es trivial, a menos que pueda enumerar rápidamente los divisores de $p-1.$
fleablood
Puntos
5913
No creo que haya nada más que ensayo y error.
Pero mira. $7^2 \equiv 23 \equiv -6 \pmod {29}$
$7^{2x} \equiv 36 \equiv 7\pmod {29}$ .
Así que $7^{2x-1} \equiv 1 \pmod {29}$ .
Sabemos por FLT que el $7^{28}\equiv 1$ por lo que para la menor potencia a la que $7$ es un múltiplo de $1$ debe ser un divisor de $28$ .
Así que $2x-1$ es un múltiplo de un divisor de $28$ . Inmediatamente tenemos $2x-1$ es impar por lo que debe ser un múltiplo de un divisor impar de $28$ .
El único divisor impar no trivial de $28$ es $7$ . Por lo tanto, pruebe a ver si $7^7\equiv 1 \pmod {29}$ . Tenemos $7^7 \equiv 1\pmod {29}$ . Eso fue una suerte. Así que tenemos $2x-1 = 7k$ y como sólo hay $7$ valores de $7^w\pmod {29}$ podríamos suponer también $x \le 6$ . así que $x = 4$ es la única opción. Intentémoslo.
$7^4 \equiv 23\pmod {29}$ .
Yep.... que funcionó.
