Solving $a^n \equiv q \pmod{p}$ for $n$ Denote $a = 11114$, $p = 44449$, $q=21433$ and note that $p$ and $q$ are primes ($a$ isn't prime).
I wish to find a natural number $n$ such that : $a^n  \equiv q\mbox{ mod }p$.
I tried to find such an $n$ but I couldn't do it... I think it has something to do with Fermat's little theorem.
I also tried writing $a^n-q=kp$ (for $k \in \mathbb{Z}$) and then looked at the equation mod $a$ and mod $q$ to try and gain more information but that didn't lead me to an answer as well.
 A: I ended up brute forcing it for the large subgroup of order 463 inside $F_p^*$. Here's a summary of my approach. Computations done with Mathematica.


*

*$p-1=32\cdot3\cdot463$

*$a=11114$ is a primitive element modulo $p$, because $a^{(p-1)/2}\equiv-1$,
$a^{(p-1)/3}\equiv -1383$ and $a^{(p-1)/463}\equiv 19164$ all modulo $p$. Therefore $n$ will be uniquely determined modulo $p-1$.

*$q^{(p-1)/3}\equiv1$, so $q$ is a cubic residue modulo $p$. Therefore $3\mid n$.

*$g_{32}=a^{(p-1)/32}\equiv14393$ is then a generator of the unique subgroup of order 32. By listing the powers of $g_{32}$ modulo $p$ we see that $q^{(p-1)/32}\equiv3541\equiv g_{32}^{27}$. Therefore $n\equiv 27\pmod{32}$.

*Putting items 3 and 4 together (a CRT step in general, but easy in this case) we see that $n\equiv 27\pmod{3\cdot32}$.

*$g_{463}=a^{(p-1)/463}\equiv19164$ is a generator of the uniques subgroup of order 463. By listing the power of $g_{463}$ modulo $p$ we see that $q^{(p-1)/463}\equiv21099\equiv g_{463}^{123}$. Therefore $n\equiv 123\pmod{463}$.

*Putting items 5 and 6 together (a CRT step in general, but a simple observation in this case) we see that $n\equiv 123\pmod{3\cdot32\cdot463}$.

*Thus we can conclude that the smallest positiv integer $n$ with the desired property is $n=123$.


The CRT allowed us to reduce the search to smaller groups. A run of baby-step/giant-step would reduce the complexity of the search further - particularly modulo $463$. Not gonna go there tonight :-)
