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](http://en.wikipedia.org/wiki/Carmichael_function)). 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.



What is the order of a in (Z/nZ)*?
You seem to have been given some misinformation so I'll answer this question although I think it is elementary. You want to find the order of $a$ modulo $n$. The prime factorization of $a$ is largely irrelevant, the prime factorization of $n$ is crucial since otherwise you don't know the order of the group. Conversely, knowing the order of $a$ for many $a$'s will allow you to factor $n$. I'll assume you can factor $n$.


If $n$ is prime, then the group is cyclic, so any factor of $n-1$ is the order of some element. There isn't much more that can be said, you can't eyeball the order except in some obvious cases such as $a=\pm 1$. If you know a factorization of $n-1$, then you can run through the divisors of $n-1$ to find the order. If you don't know the factorization of $n-1$ then brute force is basically all you can do.


If $n$ is the power of a prime $p$, then if you can compute the order modulo $p$ (say $d$), it is easy to compute it modulo $n$ by finding the highest power of $p$ dividing $a^d-1$. This is an exercise which most number theory textbooks do when discussing primitive roots modulo prime powers.


In general, you get the order modulo $n$ by factoring $n$, and using the Chinese remainder theorem to reduce to the above cases.


