power of ten modulo prime

Question

In a mathematical quiz (that I solved by computational means), I came across the problem of finding powers k of ten with a given congruence to a given prime number, $$10^k \equiv q \text{ mod } (p)$$ as eg $$10^k \equiv 46 \text{ mod } (47)$$ and I wonder if there is a generic approach to this problem.

Answer 1

This is discrete logarithm poblem. In your case there is another simple solution: You have $46 \equiv -1 \bmod {47}$. If $10$ would be a primitive root, you would have $10^{23} \equiv -1 \bmod {10},$ and $k=23$ is indeed a solution. For a general prime $p$ you would check $10^{(p-1)/2}.$

If you change your problem to $10^k \equiv 45 \bmod {47}$ a few iterations of Pollard's rho algorithm give $k=7$.