# 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.

-
This is called the discrete log problem (DLP) and has no known polynomial time algorithms to solve it. – Brandon Carter Dec 16 '11 at 21:08
Dylan Moreland I'm sorry I didn't know how to title it (I'll think harder next time, I promise). @Brandon Carter x,b (as in the link) are not just any numbers - they are prime. maybe this could help ? – Belgi Dec 16 '11 at 21:12
@Belgi: I understand that. The point I was trying to make is that you will almost certainly not be able to do this by hand. There are algorithms that have been implemented in software packages like PARI/GP (potentially Mathematica) that are able to do this. That is your best bet to get an answer. – Brandon Carter Dec 16 '11 at 21:15
The fact that $a=\frac{p+7}{4}$ surely isn't a coincidence, but I'm not sure how to put it to use here. – Zev Chonoles Dec 16 '11 at 21:16
We have $q^{(p-1)/3}\equiv 1\pmod p$ (using Mathematica to aid, but not to brute force). So we know that $n$ is divisible by $3$, if $a$ is primitive (don't know that for sure). A very curious fact is that the unique cyclic subgroup of order 6 consists of the residue classes of $\pm1, \pm 1382$ and $\pm 1383$. – Jyrki Lahtonen Dec 16 '11 at 21:45

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.

1. $p-1=32\cdot3\cdot463$
2. $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$.
3. $q^{(p-1)/3}\equiv1$, so $q$ is a cubic residue modulo $p$. Therefore $3\mid n$.
4. $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}$.
5. 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}$.
6. $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}$.
7. 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}$.
8. 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 :-)

-
The baby-step/giant-step would amount to listing, for example, the elements $g_{463}^{20j},j=0,1,\ldots,23$, then listing the elements $q^{(p−1)/463}\cdot g^{i}_{463},i=0,1,…,19$, and then looking for a match. When we find a hit: $$g_{463}^{20j_0}=q^{(p−1)/463}\cdot g^{i_0}_{463},$$ we can conclude that $n\equiv 20j_0-i_0 \pmod{463}$. IOW instead of looking for a single element within a haystack of 463, we generate two lists roughly of the size of $\sqrt{463}$, and look for a duplicate entry. – Jyrki Lahtonen Dec 17 '11 at 11:34