Compute discrete logarithm I am stuck in a problem, where i have to compute discrete logarithm without use of brute force. Here is the problem:
Given is a prime number $p=21495809$. Find $x$, if $7^{x}=14750571\, mod\, p$.
First i saw that we can factor $14750571=3\times 11\times 443\times 1009$. I guess i have to work somehow with the Chinese Remainder Theorem, but i don't know how to apply it for this problem, because the number $p$ is a prime number.
Another observation was $7^{p-1}\equiv 1\, mod\, p$ by Fermat's little theorem, but it doesn't bring anything.
Does anyone see an approach how to solve this problem? I would be glad to read your comments and ideas. 
Thank you in advance!
 A: I guess that you are supposed to take advantage of the fact that $p-1=2^{19}\cdot41$. With nothing else to go by, let's see where that takes us.
Is $7$ a primitive root? A round of repeated squaring (assuming you are allowed to use WA or a suitable CAS for this) shows that 
$$7^{(p-1)/41}=7^{2^{19}}\equiv4720468\pmod p.$$
As $p\equiv1\pmod4$ the law of quadratic reciprocity tells us that
$$
7^{(p-1)/2}\equiv\left(\frac7p\right)=\left(\frac p7\right)=\left(\frac 67\right)=-1\pmod p.
$$
This proves that $7$ is, indeed, a primitive root.
The factorization of $p-1$ tells us that $G=\Bbb{Z}_p^*$ is isomorphic to a direct product of cyclic groups $G\cong C_1\times C_2$ of respective orders $41$
and $2^{19}$. Here $C_1$ is generated by $7^{2^{19}}$ and $C_2$ is
generated by $7^{41}\equiv5651199$. With $a=14750571$ we have
$$
a^{41}\equiv 20030855\in C_2.
$$
While repeatedly squaring $a$ modularly, a phenomenal piece of luck strikes (suspected something like this, for otherwise this could become quite a chore). Namely
$$ 
a^{2^{13}}\equiv-1\pmod p. \qquad(1)
$$
This means that $a$ is of order $2^{14}$ in $G$, so $a\in C_2$.
Congruence $(1)$ actually shows that the base-7 discrete logarithm of $a$ has to be an odd multiple of $32\cdot41=1312$.
So we know that $a$ will be a power of $7^{1312}\equiv 14750571$. Well, well, TBrendle already told us this bit, so... Let me conclude by outlining how we could do the rest, if we had had $7^{1312}\equiv b\not\equiv a$.
We know that
$$
a\equiv b^s,
$$
where $s=1+\sum_{i=1}^{13} s_i2^i$, and $s_i\in\{0,1\}$ for all $i$. We can calculate whether $s\equiv1$ or $3\pmod4$ by checking whether $(ab^{-1})^{2^{12}}=(b^{s-1})^{2^{12}}\equiv 1$ or $-1\pmod p$. This gives us $s_1$. Then we can figure out $s_2$ similarly by calculating $(ab^{-1-2s_1})^{2^{11}}$ and so on. This process can be speeded up producing, e.g. a look-up-table of eighth roots of unity in $G$ (or sixteenth - all depending how you tune it up).
If we hadn't had more than our share of luck we would have had to figure out all 19 bits of the discrete logarithm of $a$ in $C_2$. Then a similar (but shorter) calculation would have been carried out in the group $C_1$ of roots of unity of order $41$. After both of these we would then have used the Chinese Remainder Theorem to combine the logarithms from $C_1$ and $C_2$.
Moral: When attacking DLPs you use Chinese Remainder Theorem for factors of $p-1$. After all, the discrete logarithm takes values in the ring $\Bbb{Z}/(p-1)\Bbb{Z}$.
