Resolver $a^n \equiv q \pmod{p}$ para $n$

Question

Denote $a = 11114$ , $p = 44449$ , $q=21433$ y observe que $p$ y $q$ son primos ( $a$ no es primo).

Deseo encontrar un número natural $n$ tal que : $a^n \equiv q\mbox{ mod }p$ .

Intenté encontrar tal $n$ pero no pude hacerlo... Creo que tiene algo que ver con el pequeño teorema de Fermat. También intenté escribir $a^n-q=kp$ (para $k \in \mathbb{Z}$ ) y luego miramos la ecuación mod $a$ y mod $q$ para tratar de obtener más información, pero eso no me llevó a una respuesta también.

Answer 1

Terminé forzándolo para el gran subgrupo de orden 463 dentro de $F_p^*$ . He aquí un resumen de mi enfoque. Cálculos realizados con Mathematica.

1. $p-1=32\cdot3\cdot463$
2. $a=11114$ es un elemento primitivo módulo $p$ porque $a^{(p-1)/2}\equiv-1$ , $a^{(p-1)/3}\equiv -1383$ y $a^{(p-1)/463}\equiv 19164$ todos los módulos $p$ . Por lo tanto, $n$ se determinará de forma única módulo $p-1$ .
3. $q^{(p-1)/3}\equiv1$ Así que $q$ es un residuo cúbico módulo $p$ . Por lo tanto, $3\mid n$ .
4. $g_{32}=a^{(p-1)/32}\equiv14393$ es entonces un generador del único subgrupo de orden 32. Enumerando las potencias de $g_{32}$ modulo $p$ vemos que $q^{(p-1)/32}\equiv3541\equiv g_{32}^{27}$ . Por lo tanto, $n\equiv 27\pmod{32}$ .
5. Juntando los puntos 3 y 4 (un paso CRT en general, pero fácil en este caso) vemos que $n\equiv 27\pmod{3\cdot32}$ .
6. $g_{463}=a^{(p-1)/463}\equiv19164$ es un generador del subgrupo único de orden 463. Al enumerar la potencia de $g_{463}$ modulo $p$ vemos que $q^{(p-1)/463}\equiv21099\equiv g_{463}^{123}$ . Por lo tanto, $n\equiv 123\pmod{463}$ .
7. Juntando los puntos 5 y 6 (un paso de CRT en general, pero una simple observación en este caso) vemos que $n\equiv 123\pmod{3\cdot32\cdot463}$ .
8. Por lo tanto, podemos concluir que el menor número entero positivo $n$ con la propiedad deseada es $n=123$ .

El CRT nos permitió reducir la búsqueda a grupos más pequeños. Una ejecución de baby-step/giant-step reduciría aún más la complejidad de la búsqueda, sobre todo modulo $463$ . No voy a ir allí esta noche :-)