I was recently thinking about efficient algorithms for modular exponentiation. This led me to the (more interesting, in my opinion) question: > Let $1 < a < n$ be an integer relatively prime to $n$. What is the order of ${\overline{a}}$ in $\mathbb{Z}/n\mathbb{Z}^*$ (the multiplicative group of $\mathbb{Z}/n\mathbb{Z}$)? I did some Google searching, but all I could find were the obvious facts that the order should divide the order of the group $\phi(n)$ and the exponent of the group $\lambda(n)$ (see [Carmichael function][1]). I asked several people if anything more could be said, but the answers were generally: "Some people study this. It is really hard." However, I couldn't find any other references. > Is this a question that has been seriously considered? If so, what is known and does anyone have any good references? I am happy to suppose that we know *a priori* the prime factorization of both $a$ and $n$. Even given this information, is there something precise that can be said? Because this is a (potentially) open problem, it is possible that it should be a community wiki page, I am not entirely certain what the policy is there. If so, someone please wiki-hammer this, as I have not the power! It might also be deserving of the open-problem tag? **Edit**: I do in fact have the power to make community wiki posts (which I discovered by checking the faq) just not to edit someone else's. Still, I would prefer that this be a "real" question unless that is inappropriate. [1]: http://en.wikipedia.org/wiki/Carmichael_function