I have to estimate the computational complexity of some algorithm that does $\psi_q(m)$ iterations. Assume that all inputs $m$ are coprime to $q$.So I need to know what growth the $\psi(m)$ has.
What is growth of $\psi_q(m) = \min \{ p: m  (q^p1) \}$ for fixed $q$?
asymptotics;number theory
Bottom line: I expect the answer to be $\psi_q(m) = O(m)$, and this to be approximately tight: I don't expect you to be able to prove any significantly better upper bound on $\psi_q(m)$.Basically, $\psi_q(m)$ is the order of $q$ in the multiplicative group of integers modulo $m$, i.e., in $(\mathbb{Z}/m\mathbb{Z})^*$.  In other words, it is the smallest natural number $p$ such that $q^p \equiv 1 \pmod m$.The structure of $(\mathbb{Z}/m\mathbb{Z})^*$ is well-characterized: for instance, when $m$ is prime, it is cyclic of order $m-1$.  As a consequence, $\varphi(m-1)$ of the elements of this group will have order $m-1$ (where $\varphi(\cdot)$ denotes Euler's totient function).  It's known that the typical value of Euler's totient function $\varphi(r)$ for a random value of $r$ near $N$ is about $6N/\pi^2$, i.e., $\Theta(N)$; so heuristically we can expect that the typical value of $\varphi(m-1)$ will be $\Theta(m)$ (roughly some constant times $m$).  See, e.g., this summary on Wikipedia.In particular, when $m$ is a random prime, close to half of all elements of $(\mathbb{Z}/m\mathbb{Z})^*$ have order $m-1$: or to say this in a more careful way, we should expect that a constant fraction of group elements will have order $m-1$.  This means that, for a randomly chosen element of $(\mathbb{Z}/m\mathbb{Z})^*$, the average order will be $\Theta(m)$.  Of course, $q$ is not a random element -- it is a fixed number -- but as $m$ gets large, we can heuristically treat $q$ as a  random element of $(\mathbb{Z}/m\mathbb{Z})^*$.Moreover, the primes are relatively dense among all the integers.  (And even for a random composite, I think the same is still true: a randomly chosen element of $(\mathbb{Z}/m\mathbb{Z})^*$ will have expected order $\Theta(m)$.)Therefore, heuristically, I think $\psi_q(m) = O(m)$ is about the best bound you're going to be able to get.  This entire argument is based upon heuristics and is not something I can prove formally, but I think it should give an estimate that's good enough for evaluating the running time of your algorithm.