Cheap and Secure Web Hosting Provider : See Now

# What is growth of $\psi_q(m) = \min \{ p: m ∣ (q^p−1) \}$ for fixed $q$?

, ,
Problem Detail:

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.

###### Asked By : Piotr Semenov

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.

Question Source : http://cs.stackexchange.com/questions/18033

3200 people like this