Are there any efficient algorithms for solving the following problem?
Let $b \leq m < n$, what is the smallest value for $k \geq 1$ such that $m^k$ mod $n$ is in the range $[0,b)$.
A variant on this which would also be of interest is what is the smallest value for $k$ such that $mx^k$ mod $n$ is in the range $[0,b)$ for a given $x$ (for general values of $x$ or for specific values or having a specific property).