I have my Network Security finals. In elgamal cryptosystem, I am often encountering these equations like this
3 = (10^XA) mod 19
now everywhere I am finding only method to solve it, where I start at 0 and keep changing value for XA until the equation satisfies.
Is there any better method to solve using pen and paper + calculator?
Turns out, Discrete log is a very hard problem to solve in general. So chances are that brute force is probably your best friend. However, if you're faced with indices larger than $19$ (I don't know what a good threshold for switching tactics is), consider trying the Baby step giant step algorithm.
Although there is no known efficient algorithm, there are usually some tricks that can be applied to specific cases. In this particular problem, it's equivalent to find $n$ such that $3+19n$ is a power of $10$.
To find $n$, let $n=\sum_{i=0}^\infty a_i10^i$, we can find $a_i$ inductively. Because $9\equiv -1\text{ mod } 10$, multiplying by $9$ mod $10$ is a permutation of digits $1, 2, 3, \cdots, 9$ (indeed it sends $x$ to $10-x$). In order for $3+19n$ to be a multiple of $10$, $a_0$ can only be $3$, and $3+19\cdot 3=60$.
Now we need to select $a_1$ such that $6+19a_1$ is a multiple of $10$, hence $a_1=6$ and $6+19a_1=120$, and $a_2$ has to be $2$, hence $12+19\cdot 2 = 50$, so $a_3$ has to be $5$ and $5+19\cdot 5 = 100$ which is already of power of $10$.
Therefore $n=5263$, and $3+19\cdot n = 10^5$. So $XA$ is $5$. In other words, we can recursively define/compute $$\begin{cases} b_0=3 &\\ a_i=b_i\text{ mod } 10 &\\ b_{i+1} = (b_i + 19a_i)/10 &\end{cases}$$
until $b_i$ is a power of $10$.
Surely this may not work for other numbers. Some knowledge for finite fields may help in other cases. For the sake of exam, XA is usally a small number, so that you can find it quickly by brutal force.
